De, Minati; Singh, Satyam Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\). (English) Zbl 07813023 Theor. Comput. Sci. 992, Article ID 114452, 17 p. (2024). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. De} and \textit{S. Singh}, Theor. Comput. Sci. 992, Article ID 114452, 17 p. (2024; Zbl 07813023) Full Text: DOI arXiv
Acharyya, Ankush; Keikha, Vahideh; Majumdar, Diptapriyo; Pandit, Supantha Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms. (English) Zbl 07807470 Theor. Comput. Sci. 990, Article ID 114402, 16 p. (2024). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Acharyya} et al., Theor. Comput. Sci. 990, Article ID 114402, 16 p. (2024; Zbl 07807470) Full Text: DOI
Liu, Gang; Wang, Haitao Geometric hitting set for line-constrained disks. (English) Zbl 07789729 Morin, Pat (ed.) et al., Algorithms and data structures. 18th international symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14079, 574-587 (2023). MSC: 68P05 68Wxx PDFBibTeX XMLCite \textit{G. Liu} and \textit{H. Wang}, Lect. Notes Comput. Sci. 14079, 574--587 (2023; Zbl 07789729) Full Text: DOI arXiv
An, Shinwoo; Cho, Kyungjin; Oh, Eunjin Faster algorithms for cycle hitting problems on disk graphs. (English) Zbl 07789694 Morin, Pat (ed.) et al., Algorithms and data structures. 18th international symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14079, 29-42 (2023). MSC: 68P05 68Wxx PDFBibTeX XMLCite \textit{S. An} et al., Lect. Notes Comput. Sci. 14079, 29--42 (2023; Zbl 07789694) Full Text: DOI arXiv
Gottlob, Georg; Lanzinger, Matthias; Pichler, Reinhard; Razgon, Igor Fractional covers of hypergraphs with bounded multi-intersection. (English) Zbl 07755522 Theor. Comput. Sci. 979, Article ID 114204, 14 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{G. Gottlob} et al., Theor. Comput. Sci. 979, Article ID 114204, 14 p. (2023; Zbl 07755522) Full Text: DOI
Hirahara, Shuichi Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. (English) Zbl 07754310 Theory Comput. 19, Paper No. 4, 61 p. (2023). MSC: 68Q15 PDFBibTeX XMLCite \textit{S. Hirahara}, Theory Comput. 19, Paper No. 4, 61 p. (2023; Zbl 07754310) Full Text: DOI
De, Minati; Singh, Satyam Hitting geometric objects online via points in \(\mathbb{Z}^d\). (English) Zbl 07724775 Zhang, Yong (ed.) et al., Computing and combinatorics. 28th international conference, COCOON 2022, Shenzhen, China, October 22–24, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13595, 537-548 (2023). MSC: 68Rxx PDFBibTeX XMLCite \textit{M. De} and \textit{S. Singh}, Lect. Notes Comput. Sci. 13595, 537--548 (2023; Zbl 07724775) Full Text: DOI
Madireddy, Raghunath Reddy; Nandy, Subhas C.; Pandit, Supantha Exact algorithms and hardness results for geometric red-blue hitting set problem. (English) Zbl 1528.68387 Li, Minming (ed.) et al., Frontiers of algorithmic wisdom. International joint conference, IJTCS-FAW 2022, Hong Kong, China, August 15–19, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13461, 176-191 (2023). MSC: 68U05 68Q17 68W40 PDFBibTeX XMLCite \textit{R. R. Madireddy} et al., Lect. Notes Comput. Sci. 13461, 176--191 (2023; Zbl 1528.68387) Full Text: DOI
Bishnu, Arijit; Ghosh, Arijit; Kolay, Sudeshna; Mishra, Gopinath; Saurabh, Saket Almost optimal query algorithm for hitting set using a subset query. (English) Zbl 07709775 J. Comput. Syst. Sci. 137, 50-65 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Bishnu} et al., J. Comput. Syst. Sci. 137, 50--65 (2023; Zbl 07709775) Full Text: DOI
Dey, Sanjana; Foucaud, Florent; Nandy, Subhas C.; Sen, Arunabha Complexity and approximation for discriminating and identifying code problems in geometric setups. (English) Zbl 07704063 Algorithmica 85, No. 7, 1850-1882 (2023). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{S. Dey} et al., Algorithmica 85, No. 7, 1850--1882 (2023; Zbl 07704063) Full Text: DOI arXiv
Araújo, Júlio; Bougeret, Marin; Campos, Victor A.; Sau, Ignasi Parameterized complexity of computing maximum minimal blocking and hitting sets. (English) Zbl 1507.68222 Algorithmica 85, No. 2, 444-491 (2023). MSC: 68R10 05C69 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{J. Araújo} et al., Algorithmica 85, No. 2, 444--491 (2023; Zbl 1507.68222) Full Text: DOI arXiv
Agarwal, Pankaj; Chang, Hsien-Chih; Suri, Subhash; Xiao, Allen; Xue, Jie Dynamic geometric set cover and hitting set. (English) Zbl 07758434 ACM Trans. Algorithms 18, No. 4, Paper No. 40, 37 p. (2022). MSC: 68-XX PDFBibTeX XMLCite \textit{P. Agarwal} et al., ACM Trans. Algorithms 18, No. 4, Paper No. 40, 37 p. (2022; Zbl 07758434) Full Text: DOI arXiv
Doron, Dean; Ta-Shma, Amnon; Tell, Roei On hitting-set generators for polynomials that vanish rarely. (English) Zbl 07622848 Comput. Complexity 31, No. 2, Paper No. 16, 62 p. (2022). MSC: 68Q87 11T06 PDFBibTeX XMLCite \textit{D. Doron} et al., Comput. Complexity 31, No. 2, Paper No. 16, 62 p. (2022; Zbl 07622848) Full Text: DOI
Bannach, Max; Heinrich, Zacharias; Reischuk, Rüdiger; Tantau, Till Dynamic kernels for hitting sets and set packing. (English) Zbl 07608296 Algorithmica 84, No. 11, 3459-3488 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{M. Bannach} et al., Algorithmica 84, No. 11, 3459--3488 (2022; Zbl 07608296) Full Text: DOI
Bhargava, Vishwas; Ghosh, Sumanta Improved hitting set for orbit of ROABPs. (English) Zbl 07605018 Comput. Complexity 31, No. 2, Paper No. 15, 45 p. (2022). MSC: 68W30 PDFBibTeX XMLCite \textit{V. Bhargava} and \textit{S. Ghosh}, Comput. Complexity 31, No. 2, Paper No. 15, 45 p. (2022; Zbl 07605018) Full Text: DOI
Cheng, Kuan; Hoza, William M. Hitting sets give two-sided derandomization of small space. (English) Zbl 07602826 Theory Comput. 18, Paper No. 21, 32 p. (2022). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{K. Cheng} and \textit{W. M. Hoza}, Theory Comput. 18, Paper No. 21, 32 p. (2022; Zbl 07602826) Full Text: DOI
Pandit, Supantha Covering and packing of triangles intersecting a straight line. (English) Zbl 1496.90080 Discrete Appl. Math. 319, 92-110 (2022). MSC: 90C27 90C35 90C39 68Q25 PDFBibTeX XMLCite \textit{S. Pandit}, Discrete Appl. Math. 319, 92--110 (2022; Zbl 1496.90080) Full Text: DOI
Gottschau, Marinus; Leichter, Marilena Minimum hitting set of interval bundles problem: computational complexity and approximability. (English) Zbl 07567460 Algorithmica 84, No. 8, 2222-2239 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{M. Gottschau} and \textit{M. Leichter}, Algorithmica 84, No. 8, 2222--2239 (2022; Zbl 07567460) Full Text: DOI
Guo, Zeyu; Kumar, Mrinal; Saptharishi, Ramprasad; Solomon, Noam Derandomization from algebraic hardness. (English) Zbl 07516623 SIAM J. Comput. 51, No. 2, 315-335 (2022). MSC: 68Q17 68W20 12Y05 PDFBibTeX XMLCite \textit{Z. Guo} et al., SIAM J. Comput. 51, No. 2, 315--335 (2022; Zbl 07516623) Full Text: DOI arXiv
Rodler, Patrick Memory-limited model-based diagnosis. (English) Zbl 07505980 Artif. Intell. 305, Article ID 103681, 36 p. (2022). MSC: 68Txx PDFBibTeX XMLCite \textit{P. Rodler}, Artif. Intell. 305, Article ID 103681, 36 p. (2022; Zbl 07505980) Full Text: DOI
Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently enumerating hitting sets of hypergraphs arising in data profiling. (English) Zbl 1478.68219 J. Comput. Syst. Sci. 124, 192-213 (2022). MSC: 68R10 05C30 05C65 05C85 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{T. Bläsius} et al., J. Comput. Syst. Sci. 124, 192--213 (2022; Zbl 1478.68219) Full Text: DOI Link
Manuel, Paul; Brešar, Boštjan; Klavžar, Sandi The geodesic-transversal problem. (English) Zbl 1510.68082 Appl. Math. Comput. 413, Article ID 126621, 11 p. (2022). MSC: 68R10 05C69 05C85 68Q17 PDFBibTeX XMLCite \textit{P. Manuel} et al., Appl. Math. Comput. 413, Article ID 126621, 11 p. (2022; Zbl 1510.68082) Full Text: DOI arXiv
Bannach, Max; Heinrich, Zacharias; Reischuk, Rüdiger; Tantau, Till Dynamic kernels for hitting sets and set packing. (English) Zbl 07803585 Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 7, 18 p. (2021). MSC: 68Q25 68Q27 68Wxx PDFBibTeX XMLCite \textit{M. Bannach} et al., LIPIcs -- Leibniz Int. Proc. Inform. 214, Article 7, 18 p. (2021; Zbl 07803585) Full Text: DOI
Hébert-Johnson, Úrsula; Sonar, Chinmay; Suri, Subhash; Surianarayanan, Vaishali Anonymity-preserving space partitions. (English) Zbl 07788605 Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 32, 16 p. (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{Ú. Hébert-Johnson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 212, Article 32, 16 p. (2021; Zbl 07788605) Full Text: DOI
Bhargava, Vishwas; Ghosh, Sumanta Improved hitting set for orbit of ROABPs. (English) Zbl 07768375 Wootters, Mary (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 24th international conference, APPROX 2021, and 25th international conference, RANDOM 2021, University of Washington, Seattle, Washington, US (virtual conference), August 16–18, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 207, Article 30, 23 p. (2021). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{V. Bhargava} and \textit{S. Ghosh}, LIPIcs -- Leibniz Int. Proc. Inform. 207, Article 30, 23 p. (2021; Zbl 07768375) Full Text: DOI
Dutta, Pranjal; Dwivedi, Prateek; Saxena, Nitin Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. (English) Zbl 07711593 Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 11, 27 p. (2021). MSC: 68Q25 PDFBibTeX XMLCite \textit{P. Dutta} et al., LIPIcs -- Leibniz Int. Proc. Inform. 200, Article 11, 27 p. (2021; Zbl 07711593) Full Text: DOI arXiv
Gupta, Sushmita; Jain, Pallavi; Petety, Aditya; Singh, Sagar Parameterized complexity of \(d\)-hitting set with quotas. (English) Zbl 1490.68122 Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 293-307 (2021). MSC: 68Q27 68R10 90C27 PDFBibTeX XMLCite \textit{S. Gupta} et al., Lect. Notes Comput. Sci. 12607, 293--307 (2021; Zbl 1490.68122) Full Text: DOI
Šíma, Jiří; Žák, Stanislav A polynomial-time construction of a hitting set for read-once branching programs of width 3. (English) Zbl 1522.68176 Fundam. Inform. 184, No. 4, 307-354 (2021). MSC: 68P05 68W20 PDFBibTeX XMLCite \textit{J. Šíma} and \textit{S. Žák}, Fundam. Inform. 184, No. 4, 307--354 (2021; Zbl 1522.68176) Full Text: DOI arXiv
Bisht, Pranav; Saxena, Nitin Blackbox identity testing for sum of special ROABPs and its border class. (English) Zbl 1522.68239 Comput. Complexity 30, No. 1, Paper No. 8, 48 p. (2021). MSC: 68Q25 68Q06 68W20 68W30 PDFBibTeX XMLCite \textit{P. Bisht} and \textit{N. Saxena}, Comput. Complexity 30, No. 1, Paper No. 8, 48 p. (2021; Zbl 1522.68239) Full Text: DOI
Mitchell, Joseph S. B.; Pandit, Supantha Minimum membership covering and hitting. (English) Zbl 1516.68110 Theor. Comput. Sci. 876, 1-11 (2021). MSC: 68U05 68Q17 68W40 PDFBibTeX XMLCite \textit{J. S. B. Mitchell} and \textit{S. Pandit}, Theor. Comput. Sci. 876, 1--11 (2021; Zbl 1516.68110) Full Text: DOI
Soto, José A.; Telha, Claudio Independent sets and hitting sets of bicolored rectangular families. (English) Zbl 1519.68306 Algorithmica 83, No. 6, 1918-1952 (2021). MSC: 68U05 68Q17 68R10 PDFBibTeX XMLCite \textit{J. A. Soto} and \textit{C. Telha}, Algorithmica 83, No. 6, 1918--1952 (2021; Zbl 1519.68306) Full Text: DOI arXiv
Dey, Sanjana; Foucaud, Florent; Nandy, Subhas C.; Sen, Arunabha Discriminating codes in geometric setups. (English) Zbl 07765382 Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 24, 16 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. Dey} et al., LIPIcs -- Leibniz Int. Proc. Inform. 181, Article 24, 16 p. (2020; Zbl 07765382) Full Text: DOI
Agarwal, Pankaj K.; Chang, Hsien-Chih; Suri, Subhash; Xiao, Allen; Xue, Jie Dynamic geometric set cover and hitting set. (English) Zbl 07760131 Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 2, 15 p. (2020). MSC: 68U05 68-06 68P05 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 164, Article 2, 15 p. (2020; Zbl 07760131) Full Text: DOI
Bannach, Max; Skambath, Malte; Tantau, Till Kernelizing the hitting set problem in linear sequential and constant parallel time. (English) Zbl 07759277 Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 9, 16 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{M. Bannach} et al., LIPIcs -- Leibniz Int. Proc. Inform. 162, Article 9, 16 p. (2020; Zbl 07759277) Full Text: DOI
Hirahara, Shuichi; Watanabe, Osamu On nonadaptive security reductions of hitting set generators. (English) Zbl 07758317 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 15, 14 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{S. Hirahara} and \textit{O. Watanabe}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 15, 14 p. (2020; Zbl 07758317) Full Text: DOI
Bläser, Markus; Pandey, Anurag Polynomial identity testing for low degree polynomials with optimal randomness. (English) Zbl 07758310 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 8, 13 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{M. Bläser} and \textit{A. Pandey}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 8, 13 p. (2020; Zbl 07758310) Full Text: DOI
Doron, Dean; Ta-Shma, Amnon; Tell, Roei On hitting-set generators for polynomials that vanish rarely. (English) Zbl 07758309 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 7, 23 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{D. Doron} et al., LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 7, 23 p. (2020; Zbl 07758309) Full Text: DOI
Guo, Zeyu; Gurjar, Rohit Improved explicit hitting-sets for ROABPs. (English) Zbl 07758306 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 4, 16 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{Z. Guo} and \textit{R. Gurjar}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 4, 16 p. (2020; Zbl 07758306) Full Text: DOI
Hirahara, Shuichi Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. (English) Zbl 07561748 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 20, 47 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{S. Hirahara}, LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 20, 47 p. (2020; Zbl 07561748) Full Text: DOI
Berg, Jeremias; Bacchus, Fahiem; Poole, Alex Abstract cores in implicit hitting set MaxSat solving. (English) Zbl 07331027 Pulina, Luca (ed.) et al., Theory and applications of satisfiability testing – SAT 2020. 23rd international conference, Alghero, Italy, July 3–10, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12178, 277-294 (2020). MSC: 68Q25 68R07 68T20 PDFBibTeX XMLCite \textit{J. Berg} et al., Lect. Notes Comput. Sci. 12178, 277--294 (2020; Zbl 07331027) Full Text: DOI
Barbero, Florian; Isenmann, Lucas; Thiebaut, Jocelyn On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs. (English) Zbl 1452.68131 Algorithmica 82, No. 8, 2243-2266 (2020). MSC: 68R10 05C12 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{F. Barbero} et al., Algorithmica 82, No. 8, 2243--2266 (2020; Zbl 1452.68131) Full Text: DOI
Abu-Khzam, Faisal N.; Bazgan, Cristina; Fernau, Henning Parameterized dynamic variants of red-blue dominating set. (English) Zbl 1440.68134 Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 236-247 (2020). MSC: 68Q27 05C69 PDFBibTeX XMLCite \textit{F. N. Abu-Khzam} et al., Lect. Notes Comput. Sci. 12011, 236--247 (2020; Zbl 1440.68134) Full Text: DOI Link
Bannach, Max; Tantau, Till Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits. (English) Zbl 1433.68177 Theory Comput. Syst. 64, No. 3, 374-399 (2020). MSC: 68Q27 05C65 68Q06 68W10 68W40 90C27 PDFBibTeX XMLCite \textit{M. Bannach} and \textit{T. Tantau}, Theory Comput. Syst. 64, No. 3, 374--399 (2020; Zbl 1433.68177) Full Text: DOI
Huang, Lingxiao; Li, Jian; Shi, Qicai Approximation algorithms for the connected sensor cover problem. (English) Zbl 1436.68383 Theor. Comput. Sci. 809, 563-574 (2020). MSC: 68U05 68M18 68W25 PDFBibTeX XMLCite \textit{L. Huang} et al., Theor. Comput. Sci. 809, 563--574 (2020; Zbl 1436.68383) Full Text: DOI arXiv
Červený, Radovan; Suchý, Ondřej Faster FPT algorithm for 5-path vertex cover. (English) Zbl 07561676 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 32, 13 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{R. Červený} and \textit{O. Suchý}, LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 32, 13 p. (2019; Zbl 07561676) Full Text: DOI arXiv
Barbero, Florian; Isenmann, Lucas; Thiebaut, Jocelyn On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. (English) Zbl 1520.68107 Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 10, 14 p. (2019). MSC: 68R10 05C12 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{F. Barbero} et al., LIPIcs -- Leibniz Int. Proc. Inform. 115, Article 10, 14 p. (2019; Zbl 1520.68107) Full Text: DOI arXiv
Mitchell, Joseph S. B.; Pandit, Supantha New results on a family of geometric hitting set problems in the plane. (English) Zbl 1435.68350 Li, Yingshu (ed.) et al., Combinatorial optimization and applications. 13th international conference, COCOA 2019, Xiamen, China, December 13–15, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11949, 387-399 (2019). MSC: 68U05 68Q17 68W25 PDFBibTeX XMLCite \textit{J. S. B. Mitchell} and \textit{S. Pandit}, Lect. Notes Comput. Sci. 11949, 387--399 (2019; Zbl 1435.68350) Full Text: DOI
Guo, Zeyu; Saxena, Nitin; Sinhababu, Amit Algebraic dependencies and \(\mathsf{PSPACE}\) algorithms in approximative complexity over any field. (English) Zbl 1456.68058 Theory Comput. 15, Paper No. 16, 30 p. (2019). MSC: 68Q25 11T06 14Q20 68W30 PDFBibTeX XMLCite \textit{Z. Guo} et al., Theory Comput. 15, Paper No. 16, 30 p. (2019; Zbl 1456.68058) Full Text: DOI
Cicerone, Serafino; Di Stefano, Gabriele; Gasieniec, Leszek; Jurdzinski, Tomasz; Navarra, Alfredo; Radzik, Tomasz; Stachowiak, Grzegorz Fair hitting sequence problem: scheduling activities with varied frequency requirements. (English) Zbl 1525.90195 Heggernes, Pinar (ed.), Algorithms and complexity. 11th international conference, CIAC 2019, Rome, Italy, May 27–29, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11485, 174-186 (2019). MSC: 90B35 68Q17 68W25 90B25 PDFBibTeX XMLCite \textit{S. Cicerone} et al., Lect. Notes Comput. Sci. 11485, 174--186 (2019; Zbl 1525.90195) Full Text: DOI
Mitchell, Joseph S. B.; Pandit, Supantha Minimum membership covering and hitting. (English) Zbl 1522.68664 Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 394-406 (2019). MSC: 68U05 68Q17 68W25 PDFBibTeX XMLCite \textit{J. S. B. Mitchell} and \textit{S. Pandit}, Lect. Notes Comput. Sci. 11355, 394--406 (2019; Zbl 1522.68664) Full Text: DOI
Pandit, Supantha Covering and packing of triangles intersecting a straight line. (English) Zbl 1522.68671 Pal, Sudebkumar Prasant (ed.) et al., Algorithms and discrete applied mathematics. 5th international conference, CALDAM 2019, Kharagpur, India, February 14–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11394, 216-230 (2019). MSC: 68U05 68Q17 68W40 PDFBibTeX XMLCite \textit{S. Pandit}, Lect. Notes Comput. Sci. 11394, 216--230 (2019; Zbl 1522.68671) Full Text: DOI
Fomin, Fedor V.; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomassé, Stéphan; Zehavi, Meirav Subquadratic kernels for implicit 3-{Hitting Set} and 3-{Set Packing} problems. (English) Zbl 1454.68101 ACM Trans. Algorithms 15, No. 1, Article No. 13, 44 p. (2019). MSC: 68R10 68Q27 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., ACM Trans. Algorithms 15, No. 1, Article No. 13, 44 p. (2019; Zbl 1454.68101) Full Text: DOI
Madireddy, Raghunath Reddy; Mudgal, Apurva Approximability and hardness of geometric hitting set with axis-parallel rectangles. (English) Zbl 1478.68424 Inf. Process. Lett. 141, 9-15 (2019). MSC: 68U05 52C15 68Q17 68W25 PDFBibTeX XMLCite \textit{R. R. Madireddy} and \textit{A. Mudgal}, Inf. Process. Lett. 141, 9--15 (2019; Zbl 1478.68424) Full Text: DOI
Madireddy, Raghunath Reddy; Mudgal, Apurva \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point. (English) Zbl 1478.68423 Inf. Process. Lett. 141, 1-8 (2019). MSC: 68U05 52C15 68Q17 PDFBibTeX XMLCite \textit{R. R. Madireddy} and \textit{A. Mudgal}, Inf. Process. Lett. 141, 1--8 (2019; Zbl 1478.68423) Full Text: DOI
Bishnu, Arijit; Ghosh, Arijit; Kolay, Sudeshna; Mishra, Gopinath; Saurabh, Saket Parameterized query complexity of hitting set using stability of sunflowers. (English) Zbl 07561379 Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 25, 12 p. (2018). MSC: 68Wxx PDFBibTeX XMLCite \textit{A. Bishnu} et al., LIPIcs -- Leibniz Int. Proc. Inform. 123, Article 25, 12 p. (2018; Zbl 07561379) Full Text: DOI arXiv
Forbes, Michael A.; Ghosh, Sumanta; Saxena, Nitin Towards blackbox identity testing of log-variate circuits. (English) Zbl 1499.68390 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 54, 16 p. (2018). MSC: 68W20 68Q06 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 54, 16 p. (2018; Zbl 1499.68390) Full Text: DOI
Guo, Zeyu; Saxena, Nitin; Sinhababu, Amit Algebraic dependencies and PSPACE algorithms in approximative complexity. (English) Zbl 1442.68062 Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 10, 21 p. (2018). MSC: 68Q15 14Q20 68Q25 PDFBibTeX XMLCite \textit{Z. Guo} et al., LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 10, 21 p. (2018; Zbl 1442.68062) Full Text: DOI arXiv
Boissonnat, Jean-Daniel; Dutta, Kunal; Ghosh, Arijit; Kolay, Sudeshna Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set. (English) Zbl 1485.68264 Bender, Michael A. (ed.) et al., Latin 2018: theoretical informatics. 13th Latin American symposium, Buenos Aires, Argentina, April 16–19, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10807, 187-200 (2018). MSC: 68U05 68Q27 PDFBibTeX XMLCite \textit{J.-D. Boissonnat} et al., Lect. Notes Comput. Sci. 10807, 187--200 (2018; Zbl 1485.68264) Full Text: DOI Link
Forbes, Michael A.; Shpilka, Amir A PSPACE construction of a hitting set for the closure of small algebraic circuits. (English) Zbl 1428.68171 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180-1192 (2018). MSC: 68Q25 68Q06 PDFBibTeX XMLCite \textit{M. A. Forbes} and \textit{A. Shpilka}, in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180--1192 (2018; Zbl 1428.68171) Full Text: DOI arXiv
Agrawal, Manindra; Ghosh, Sumanta; Saxena, Nitin Bootstrapping variables in algebraic circuits. (English) Zbl 1427.68356 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1166-1179 (2018). MSC: 68W20 68Q17 68Q25 94C11 PDFBibTeX XMLCite \textit{M. Agrawal} et al., in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1166--1179 (2018; Zbl 1427.68356) Full Text: DOI
Kobylkin, K. S. Computational complexity for the problem of optimal intersection of straight line segments by disks. (English. Russian original) Zbl 1414.05093 Proc. Steklov Inst. Math. 303, Suppl. 1, S146-S155 (2018); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 23, No. 3, 171-181 (2017). MSC: 05C10 05C62 68Q17 PDFBibTeX XMLCite \textit{K. S. Kobylkin}, Proc. Steklov Inst. Math. 303, S146--S155 (2018; Zbl 1414.05093); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 23, No. 3, 171--181 (2017) Full Text: DOI
Agrawal, Akanksha; Choudhary, Pratibha; Jain, Pallavi; Kanesh, Lawqueen; Sahlot, Vibha; Saurabh, Saket Hitting and covering partially. (English) Zbl 1509.68106 Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 751-763 (2018). MSC: 68Q27 68Q17 68R10 90C27 PDFBibTeX XMLCite \textit{A. Agrawal} et al., Lect. Notes Comput. Sci. 10976, 751--763 (2018; Zbl 1509.68106) Full Text: DOI
Fekete, Sándor P.; Huang, Kan; Mitchell, Joseph S. B.; Parekh, Ojas; Phillips, Cynthia A. Geometric hitting set for segments of few orientations. (English) Zbl 1384.68021 Theory Comput. Syst. 62, No. 2, 268-303 (2018). MSC: 68U05 68W25 PDFBibTeX XMLCite \textit{S. P. Fekete} et al., Theory Comput. Syst. 62, No. 2, 268--303 (2018; Zbl 1384.68021) Full Text: DOI arXiv
Gaspers, Serge; Lee, Edward J. Exact algorithms via multivariate subroutines. (English) Zbl 1441.68181 Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 69, 13 p. (2017). MSC: 68R10 05C85 68W20 68W40 PDFBibTeX XMLCite \textit{S. Gaspers} and \textit{E. J. Lee}, LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 69, 13 p. (2017; Zbl 1441.68181) Full Text: DOI arXiv
Tell, Roei Improved bounds for quantified derandomization of constant-depth circuits and polynomials. (English) Zbl 1440.68131 O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 13, 48 p. (2017). MSC: 68Q25 68Q06 68Q17 68W20 PDFBibTeX XMLCite \textit{R. Tell}, LIPIcs -- Leibniz Int. Proc. Inform. 79, Article 13, 48 p. (2017; Zbl 1440.68131) Full Text: DOI
Agarwal, Pankaj K.; Kumar, Nirman; Sintos, Stavros; Suri, Subhash Efficient algorithms for \(k\)-regret minimizing sets. (English) Zbl 1432.68112 Iliopoulos, Costas S. (ed.) et al., 16th international symposium on experimental algorithms, SEA 2017, London, UK, June 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 75, Article 7, 23 p. (2017). MSC: 68P15 68W25 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 75, Article 7, 23 p. (2017; Zbl 1432.68112) Full Text: DOI arXiv
Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket Quick but odd growth of cacti. (English) Zbl 1372.68136 Algorithmica 79, No. 1, 271-290 (2017). MSC: 68Q25 05C75 05C85 68W20 PDFBibTeX XMLCite \textit{S. Kolay} et al., Algorithmica 79, No. 1, 271--290 (2017; Zbl 1372.68136) Full Text: DOI Link
Shachnai, Hadas; Zehavi, Meirav A multivariate framework for weighted FPT algorithms. (English) Zbl 1372.68145 J. Comput. Syst. Sci. 89, 157-189 (2017). MSC: 68Q25 05C69 05C70 05C85 PDFBibTeX XMLCite \textit{H. Shachnai} and \textit{M. Zehavi}, J. Comput. Syst. Sci. 89, 157--189 (2017; Zbl 1372.68145) Full Text: DOI arXiv
Guruswami, Venkatesan; Lee, Euiwoong Nearly optimal NP-hardness of unique coverage. (English) Zbl 1371.68098 SIAM J. Comput. 46, No. 3, 1018-1028 (2017). MSC: 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{V. Guruswami} and \textit{E. Lee}, SIAM J. Comput. 46, No. 3, 1018--1028 (2017; Zbl 1371.68098) Full Text: DOI
Mouawad, Amer E.; Nishimura, Naomi; Raman, Venkatesh; Simjour, Narges; Suzuki, Akira On the parameterized complexity of reconfiguration problems. (English) Zbl 1360.68516 Algorithmica 78, No. 1, 274-297 (2017). MSC: 68Q25 68Q17 90C35 PDFBibTeX XMLCite \textit{A. E. Mouawad} et al., Algorithmica 78, No. 1, 274--297 (2017; Zbl 1360.68516) Full Text: DOI arXiv
Jansen, Bart M. P. On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT. (English) Zbl 1358.05281 J. Graph Algorithms Appl. 21, No. 2, 219-243 (2017). MSC: 05C85 05C38 90C27 68Q17 PDFBibTeX XMLCite \textit{B. M. P. Jansen}, J. Graph Algorithms Appl. 21, No. 2, 219--243 (2017; Zbl 1358.05281) Full Text: DOI arXiv
Bazzi, Louay; Nahas, Nagi Small-bias is not enough to hit read-once CNF. (English) Zbl 1364.68300 Theory Comput. Syst. 60, No. 2, 324-345 (2017). MSC: 68Q87 68Q25 PDFBibTeX XMLCite \textit{L. Bazzi} and \textit{N. Nahas}, Theory Comput. Syst. 60, No. 2, 324--345 (2017; Zbl 1364.68300) Full Text: DOI
Gainer-Dewar, Andrew; Vera-Licona, Paola The minimal hitting set generation problem: algorithms and computation. (English) Zbl 1352.68279 SIAM J. Discrete Math. 31, No. 1, 63-100 (2017). MSC: 68W05 68R05 PDFBibTeX XMLCite \textit{A. Gainer-Dewar} and \textit{P. Vera-Licona}, SIAM J. Discrete Math. 31, No. 1, 63--100 (2017; Zbl 1352.68279) Full Text: DOI arXiv
Damaschke, Peter Refined algorithms for hitting many intervals. (English) Zbl 1393.68128 Inf. Process. Lett. 118, 117-122 (2017). MSC: 68R05 68R10 68W40 90B35 90C39 PDFBibTeX XMLCite \textit{P. Damaschke}, Inf. Process. Lett. 118, 117--122 (2017; Zbl 1393.68128) Full Text: DOI
Khachai, Daniel M.; Khachay, Michael Yu. On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line. (English) Zbl 1396.68127 Ural Math. J. 2, No. 2, 117-126 (2016). MSC: 68U05 68Q25 68W40 PDFBibTeX XMLCite \textit{D. M. Khachai} and \textit{M. Yu. Khachay}, Ural Math. J. 2, No. 2, 117--126 (2016; Zbl 1396.68127) Full Text: DOI MNR
Agarwal, Pankaj K.; Pan, Jiangwei; Victor, Will An efficient algorithm for placing electric vehicle charging stations. (English) Zbl 1398.68657 Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 7, 12 p. (2016). MSC: 68W25 05C38 68P05 90B80 90C27 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 64, Article 7, 12 p. (2016; Zbl 1398.68657) Full Text: DOI
Hązła, Jan; Holenstein, Thomas; Mossel, Elchanan Lower bounds on same-set inner product in correlated spaces. (English) Zbl 1398.60020 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 19th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2016, and the 20th international workshop on randomization and computation, RANDOM 2016, Paris, France, September 7–9, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-018-7). LIPIcs – Leibniz International Proceedings in Informatics 60, Article 34, 11 p. (2016). MSC: 60C05 05D40 68Q17 PDFBibTeX XMLCite \textit{J. Hązła} et al., LIPIcs -- Leibniz Int. Proc. Inform. 60, Article 34, 11 p. (2016; Zbl 1398.60020) Full Text: DOI
Bringmann, Karl; Kozma, László; Moran, Shay; Narayanaswamy, N. S. Hitting set for hypergraphs of low VC-dimension. (English) Zbl 1397.68092 Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 23, 18 p. (2016). MSC: 68Q25 05C65 68Q17 68U05 PDFBibTeX XMLCite \textit{K. Bringmann} et al., LIPIcs -- Leibniz Int. Proc. Inform. 57, Article 23, 18 p. (2016; Zbl 1397.68092) Full Text: DOI arXiv
Bonnet, Édouard; Miltzow, Tillmann Parameterized hardness of art gallery problems. (English) Zbl 1397.68091 Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 19, 17 p. (2016). MSC: 68Q25 68Q17 68U05 PDFBibTeX XMLCite \textit{É. Bonnet} and \textit{T. Miltzow}, LIPIcs -- Leibniz Int. Proc. Inform. 57, Article 19, 17 p. (2016; Zbl 1397.68091) Full Text: DOI arXiv
Bhattiprolu, Vijay V. S. P.; Har-Peled, Sariel Separating a Voronoi diagram via local search. (English) Zbl 1387.68240 Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 18, 16 p. (2016). MSC: 68U05 68W25 PDFBibTeX XMLCite \textit{V. V. S. P. Bhattiprolu} and \textit{S. Har-Peled}, LIPIcs -- Leibniz Int. Proc. Inform. 51, Article 18, 16 p. (2016; Zbl 1387.68240) Full Text: DOI arXiv
Ignatiev, Alexey; Morgado, Antonio; Planes, Jordi; Marques-Silva, Joao Maximal falsifiability. Definitions, algorithms and applications. (English) Zbl 1373.68378 AI Commun. 29, No. 2, 351-370 (2016). MSC: 68T20 90C09 90C59 PDFBibTeX XMLCite \textit{A. Ignatiev} et al., AI Commun. 29, No. 2, 351--370 (2016; Zbl 1373.68378) Full Text: DOI
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin Identity testing for constant-width, and commutative, read-once oblivious ABPs. (English) Zbl 1380.68224 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 29, 16 p. (2016). MSC: 68Q25 12Y05 68P05 PDFBibTeX XMLCite \textit{R. Gurjar} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 29, 16 p. (2016; Zbl 1380.68224) Full Text: DOI
Artemenko, Sergei; Impagliazzo, Russell; Kabanets, Valentine; Shaltiel, Ronen Pseudorandomness when the odds are against you. (English) Zbl 1380.68434 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 9, 35 p. (2016). MSC: 68W20 68Q17 68Q25 PDFBibTeX XMLCite \textit{S. Artemenko} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 9, 35 p. (2016; Zbl 1380.68434) Full Text: DOI
Mudgal, Apurva; Pandit, Supantha Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions. (English) Zbl 1348.05050 Discrete Appl. Math. 211, 143-162 (2016). MSC: 05B40 90C39 68Q17 PDFBibTeX XMLCite \textit{A. Mudgal} and \textit{S. Pandit}, Discrete Appl. Math. 211, 143--162 (2016; Zbl 1348.05050) Full Text: DOI
Xiao, Mingyu A parameterized algorithm for bounded-degree vertex deletion. (English) Zbl 1476.68219 Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 79-91 (2016). MSC: 68R10 05C07 05C70 05C85 68Q27 68W40 PDFBibTeX XMLCite \textit{M. Xiao}, Lect. Notes Comput. Sci. 9797, 79--91 (2016; Zbl 1476.68219) Full Text: DOI arXiv
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. (English) Zbl 1388.68118 Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 323-346 (2015). MSC: 68Q25 68Q05 PDFBibTeX XMLCite \textit{R. Gurjar} et al., LIPIcs -- Leibniz Int. Proc. Inform. 33, 323--346 (2015; Zbl 1388.68118) Full Text: DOI
Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket Quick but odd growth of cacti. (English) Zbl 1372.68135 Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 258-269 (2015). MSC: 68Q25 05C75 05C85 68W20 PDFBibTeX XMLCite \textit{S. Kolay} et al., LIPIcs -- Leibniz Int. Proc. Inform. 43, 258--269 (2015; Zbl 1372.68135) Full Text: DOI
Nagarajan, Viswanath; Sarpatwar, Kanthi K.; Schieber, Baruch; Shachnai, Hadas; Wolf, Joel L. The container selection problem. (English) Zbl 1375.68034 Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 416-434 (2015). MSC: 68M20 68M14 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{V. Nagarajan} et al., LIPIcs -- Leibniz Int. Proc. Inform. 40, 416--434 (2015; Zbl 1375.68034) Full Text: DOI
Yu, Quan; Li, Chengqian; Shen, Yuming; Wang, Ju A method of solving abductive reasoning problems via hitting set. (Chinese. English summary) Zbl 1340.68160 J. Softw. 26, No. 8, 1937-1945 (2015). MSC: 68T27 68T37 PDFBibTeX XMLCite \textit{Q. Yu} et al., J. Softw. 26, No. 8, 1937--1945 (2015; Zbl 1340.68160) Full Text: DOI
Piliouras, Georgios; Valla, Tomáš; Végh, László A. LP-based covering games with low price of anarchy. (English) Zbl 1372.91017 Theory Comput. Syst. 57, No. 1, 238-260 (2015). MSC: 91A43 91A10 68W25 90C27 91B32 PDFBibTeX XMLCite \textit{G. Piliouras} et al., Theory Comput. Syst. 57, No. 1, 238--260 (2015; Zbl 1372.91017) Full Text: DOI arXiv Link
Kanj, Iyad; Zhang, Fenghui 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size. (English) Zbl 1316.05091 Discrete Math. Algorithms Appl. 7, No. 2, Article ID 1550011, 17 p. (2015). MSC: 05C65 68W01 68W40 PDFBibTeX XMLCite \textit{I. Kanj} and \textit{F. Zhang}, Discrete Math. Algorithms Appl. 7, No. 2, Article ID 1550011, 17 p. (2015; Zbl 1316.05091) Full Text: DOI
Agarwal, Pankaj K.; Pan, Jiangwei Near-linear algorithms for geometric hitting sets and set covers. (English) Zbl 1398.68656 Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 271-279 (2014). MSC: 68W25 68U05 68W05 68W20 PDFBibTeX XMLCite \textit{P. K. Agarwal} and \textit{J. Pan}, in: Proceedings of the 30th annual symposium on computational geometry, SoCG '14, Kyoto, Japan, June 8--11, 2014. New York, NY: Association for Computing Machinery (ACM). 271--279 (2014; Zbl 1398.68656) Full Text: DOI
Saxena, Nitin Progress on polynomial identity testing. II. (English) Zbl 1345.68182 Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 131-146 (2014). MSC: 68Q25 12Y05 13P05 68Q05 68Q17 68W30 68-02 PDFBibTeX XMLCite \textit{N. Saxena}, Prog. Comput. Sci. Appl. Log. 26, 131--146 (2014; Zbl 1345.68182) Full Text: DOI
Wild, Marcel Counting or producing all fixed cardinality transversals. (English) Zbl 1303.05200 Algorithmica 69, No. 1, 117-129 (2014). MSC: 05C85 05C65 05C30 05D15 68R10 11B73 PDFBibTeX XMLCite \textit{M. Wild}, Algorithmica 69, No. 1, 117--129 (2014; Zbl 1303.05200) Full Text: DOI arXiv
El Ouali, Mourad; Fohlin, Helena; Srivastav, Anand A randomised approximation algorithm for the hitting set problem. (English) Zbl 1360.68903 Theor. Comput. Sci. 555, 23-34 (2014). MSC: 68W25 05C65 05C70 05C85 68W20 PDFBibTeX XMLCite \textit{M. El Ouali} et al., Theor. Comput. Sci. 555, 23--34 (2014; Zbl 1360.68903) Full Text: DOI
Even, Guy; Smorodinsky, Shakhar Hitting sets online and unique-MAX coloring. (English) Zbl 1300.05299 Discrete Appl. Math. 178, 71-82 (2014). MSC: 05C85 05C15 05C65 05D15 68W27 PDFBibTeX XMLCite \textit{G. Even} and \textit{S. Smorodinsky}, Discrete Appl. Math. 178, 71--82 (2014; Zbl 1300.05299) Full Text: DOI arXiv
Yuan, Chen; Kan, Haibin A note on sparse solutions of sparse linear systems. (English) Zbl 1360.68521 Theor. Comput. Sci. 552, 109-111 (2014). MSC: 68Q25 05C65 65F50 PDFBibTeX XMLCite \textit{C. Yuan} and \textit{H. Kan}, Theor. Comput. Sci. 552, 109--111 (2014; Zbl 1360.68521) Full Text: DOI
McGuire, Gary; Tugemann, Bastian; Civario, Gilles There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration. (English) Zbl 1296.05008 Exp. Math. 23, No. 2, 190-217 (2014). MSC: 05A15 05B15 68Q25 PDFBibTeX XMLCite \textit{G. McGuire} et al., Exp. Math. 23, No. 2, 190--217 (2014; Zbl 1296.05008) Full Text: DOI arXiv
Lu, Min; Liu, Tian; Tong, Weitian; Lin, Guohui; Xu, Ke Set cover, set packing and hitting set for tree convex and tree-like set systems. (English) Zbl 1405.68144 Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 11th annual conference, TAMC 2014, Chennai, India, April 11–13, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-06088-0/pbk). Lecture Notes in Computer Science 8402, 248-258 (2014). MSC: 68Q25 05C05 68R05 90C27 PDFBibTeX XMLCite \textit{M. Lu} et al., Lect. Notes Comput. Sci. 8402, 248--258 (2014; Zbl 1405.68144) Full Text: DOI
Fourman, Michael Paul Hitting Buneman circles. (English) Zbl 1397.68224 Tannen, Val (ed.) et al., In search of elegance in the theory and practice of computation. Essays dedicated to Peter Buneman. Berlin: Springer (ISBN 978-3-642-41659-0/pbk; 978-3-642-41660-6/ebook). Lecture Notes in Computer Science 8000, 250-258 (2013). MSC: 68W25 68M11 90B80 PDFBibTeX XMLCite \textit{M. P. Fourman}, Lect. Notes Comput. Sci. 8000, 250--258 (2013; Zbl 1397.68224) Full Text: DOI