{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T09:27:48Z","timestamp":1774690068210,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T00:00:00Z","timestamp":1609891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EPSRC grant FptGeom","award":["EP\/N029143\/1"],"award-info":[{"award-number":["EP\/N029143\/1"]}]},{"name":"ANR grant ESIGMA","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]},{"name":"\u201cInvestissements d\u2019Avenir\u201d","award":["ANR-11-IDEX-0007"],"award-info":[{"award-number":["ANR-11-IDEX-0007"]}]},{"name":"LABEX MILYON","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["714704"],"award-info":[{"award-number":["714704"]}]},{"name":"ANR Project DISTANCIA","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for M\n            <jats:sc>AXIMUM<\/jats:sc>\n            C\n            <jats:sc>LIQUE<\/jats:sc>\n            on unit disk graphs [Clark, Colbourn, Johnson;\n            <jats:italic>Discrete Mathematics<\/jats:italic>\n            \u201990]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2\n            <jats:sup>\n              \u00d5(\n              <jats:italic>n<\/jats:italic>\n              <jats:sup>2\/3<\/jats:sup>\n              )\n            <\/jats:sup>\n            for M\n            <jats:sc>AXIMUM<\/jats:sc>\n            C\n            <jats:sc>LIQUE<\/jats:sc>\n            on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for M\n            <jats:sc>AX<\/jats:sc>\n            C\n            <jats:sc>LIQUE<\/jats:sc>\n            on disk and unit ball graphs. M\n            <jats:sc>AX<\/jats:sc>\n            C\n            <jats:sc>LIQUE<\/jats:sc>\n            on unit ball graphs is equivalent to finding, given a collection of points in R\n            <jats:sup>3<\/jats:sup>\n            , a maximum subset of points with diameter at most some fixed value.\n          <\/jats:p>\n          <jats:p>\n            In stark contrast, M\n            <jats:sc>AXIMUM<\/jats:sc>\n            C\n            <jats:sc>LIQUE<\/jats:sc>\n            on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            <jats:sup>1\u2212\u025b<\/jats:sup>\n            , unless the Exponential Time Hypothesis fails.\n          <\/jats:p>","DOI":"10.1145\/3433160","type":"journal-article","created":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T13:25:38Z","timestamp":1609939538000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs"],"prefix":"10.1145","volume":"68","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[{"name":"CNRS, LaBRI, Universit\u00e9 de Bordeaux, Bordeaux, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon (COMUE), CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP, Lyon, France"}]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[{"name":"CNRS, G-SCOP laboratory, Grenoble-INP, France"}]},{"given":"Pierre","family":"Charbit","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Diderot - IRIF, France and Universit\u00e9 de Lyon (COMUE), CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP"}]},{"given":"Panos","family":"Giannopoulos","sequence":"additional","affiliation":[{"name":"giCentre, Department of Computer Science, City University of London, London, United Kingdom"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Dauphine, PSL University, CNRS UMR, LAMSADE, Paris, France"}]},{"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland and Institute of Informatics, University of Warsaw, Warsaw, Poland"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Dauphine, PSL University, CNRS UMR, LAMSADE, Paris, France"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon (COMUE), CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP, France and Institut Universitaire de France"}]}],"member":"320","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG\u201905)","author":"Afshani Peyman","year":"2005","unstructured":"Peyman Afshani and Timothy M. Chan . 2005. Approximation algorithms for maximum cliques in 3D unit-disk graphs . In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG\u201905) . 19--22. Retrieved from http:\/\/www.cccg.ca\/proceedings\/ 2005 \/69.pdf. Peyman Afshani and Timothy M. Chan. 2005. Approximation algorithms for maximum cliques in 3D unit-disk graphs. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG\u201905). 19--22. Retrieved from http:\/\/www.cccg.ca\/proceedings\/2005\/69.pdf."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.005"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1143176.1646569"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08794"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1141-6"},{"key":"e_1_2_1_8_1","volume-title":"On pseudo-disk hypergraphs. CoRR abs\/1802.08799","author":"Aronov Boris","year":"2018","unstructured":"Boris Aronov , Anirudh Donakonda , Esther Ezra , and Rom Pinchasi . 2018. On pseudo-disk hypergraphs. CoRR abs\/1802.08799 ( 2018 ). Boris Aronov, Anirudh Donakonda, Esther Ezra, and Rom Pinchasi. 2018. On pseudo-disk hypergraphs. CoRR abs\/1802.08799 (2018)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055473"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-9968-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33700-8_30"},{"key":"e_1_2_1_12_1","first-page":"47","article-title":"Fine-grained complexity of coloring unit disks and balls","volume":"9","author":"Bir\u00f3 Csaba","year":"2018","unstructured":"Csaba Bir\u00f3 , \u00c9douard Bonnet , D\u00e1niel Marx , Tillmann Miltzow , and Pawe\u0142 Rz\u0105\u017cewski . 2018 . Fine-grained complexity of coloring unit disks and balls . J. Comput. Geom. 9 , 2 (2018), 47 -- 80 . Retrieved from http:\/\/jocg.org\/index.php\/jocg\/article\/view\/414. Csaba Bir\u00f3, \u00c9douard Bonnet, D\u00e1niel Marx, Tillmann Miltzow, and Pawe\u0142 Rz\u0105\u017cewski. 2018. Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. 9, 2 (2018), 47--80. Retrieved from http:\/\/jocg.org\/index.php\/jocg\/article\/view\/414.","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201914)","author":"Bock Adrian","year":"2014","unstructured":"Adrian Bock , Yuri Faenza , Carsten Moldenhauer , and Andres J . Ruiz-Vargas. 2014. Solving the stable set problem in terms of the odd cycle packing number . In Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201914) . 187--198. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS. 2014 .187 10.4230\/LIPIcs.FSTTCS.2014.187 Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres J. Ruiz-Vargas. 2014. Solving the stable set problem in terms of the odd cycle packing number. In Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201914). 187--198. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2014.187"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00060"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918)","author":"Bonnet \u00c9douard","year":"2018","unstructured":"\u00c9douard Bonnet , Panos Giannopoulos , Eun Jung Kim , Pawe\u0142 Rz\u0105\u017cewski , and Florian Sikora . 2018 . QPTAS and subexponential algorithm for maximum clique on disk graphs . In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918) . 12:1--12:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.12 10.4230\/LIPIcs.SoCG.2018.12 \u00c9douard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawe\u0142 Rz\u0105\u017cewski, and Florian Sikora. 2018. QPTAS and subexponential algorithm for maximum clique on disk graphs. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918). 12:1--12:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.12"},{"key":"e_1_2_1_18_1","volume-title":"Van Bang Le, and Jeremy P. Spinrad","author":"Brandst\u00e4dt Andreas","year":"1999","unstructured":"Andreas Brandst\u00e4dt , Van Bang Le, and Jeremy P. Spinrad . 1999 . Graph Classes : A Survey. SIAM. Andreas Brandst\u00e4dt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes: A Survey. SIAM."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00012-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.03.046"},{"key":"e_1_2_1_21_1","unstructured":"Sergio Cabello. 2015. Maximum clique for disks of two sizes. Open problems fromGeometric Intersection Graphs: Problems and Directions CG Week Workshop. Retrieved from http:\/\/cgweek15.tcs.uj.edu.pl\/problems.pdf.  Sergio Cabello. 2015. Maximum clique for disks of two sizes. Open problems fromGeometric Intersection Graphs: Problems and Directions CG Week Workshop. Retrieved from http:\/\/cgweek15.tcs.uj.edu.pl\/problems.pdf."},{"key":"e_1_2_1_22_1","unstructured":"Sergio Cabello. 2015. Open problems presented at theAlgorithmic Graph Theory on the Adriatic Coast Workshop. Retrieved from https:\/\/conferences.matheo.si\/event\/6\/picture\/35.pdf.  Sergio Cabello. 2015. Open problems presented at theAlgorithmic Graph Theory on the Adriatic Coast Workshop. Retrieved from https:\/\/conferences.matheo.si\/event\/6\/picture\/35.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9538-5"},{"key":"e_1_2_1_24_1","volume-title":"Stabbing pairwise intersecting disks by four points. CoRR abs\/1812.06907","author":"Carmi Paz","year":"2018","unstructured":"Paz Carmi , Matthew J. Katz , and Pat Morin . 2018. Stabbing pairwise intersecting disks by four points. CoRR abs\/1812.06907 ( 2018 ). Paz Carmi, Matthew J. Katz, and Pat Morin. 2018. Stabbing pairwise intersecting disks by four points. CoRR abs\/1812.06907 (2018)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116657.3116973"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.029"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Zur l\u00f6sung des Gallaischen problems \u00fcber Kreisscheiben in der Euklidischen Ebene. Studia Sci","volume":"21","author":"Danzer L.","year":"1986","unstructured":"L. Danzer . 1986 . Zur l\u00f6sung des Gallaischen problems \u00fcber Kreisscheiben in der Euklidischen Ebene. Studia Sci . Math. Hungar 21 , 1 \u2013 2 (1986), 111--134. L. Danzer. 1986. Zur l\u00f6sung des Gallaischen problems \u00fcber Kreisscheiben in der Euklidischen Ebene. Studia Sci. Math. Hungar 21, 1\u20132 (1986), 111--134.","journal-title":"Math. Hungar"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_32_1","volume-title":"Induced odd cycle packing number, independent sets, and chromatic number. CoRR abs\/2001.02411","author":"Dvo\u0159\u00e1k Zdenek","year":"2020","unstructured":"Zdenek Dvo\u0159\u00e1k and Jakub Pek\u00e1rek . 2020. Induced odd cycle packing number, independent sets, and chromatic number. CoRR abs\/2001.02411 ( 2020 ). Zdenek Dvo\u0159\u00e1k and Jakub Pek\u00e1rek. 2020. Induced odd cycle packing number, independent sets, and chromatic number. CoRR abs\/2001.02411 (2020)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402676"},{"key":"e_1_2_1_34_1","volume-title":"Approximation and Online Algorithms","author":"Fishkin Aleksei V.","year":"2003","unstructured":"Aleksei V. Fishkin . 2003. Disk graphs: A short survey . In Approximation and Online Algorithms , First International Workshop, WAOA 2003 , Budapest, Hungary, September 16--18, 2003, Revised Papers (Lecture Notes in Computer Science), Klaus Jansen and Roberto Solis-Oba (Eds.), Vol. 2909 . Springer , 260--264. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24592-6_23 10.1007\/978-3-540-24592-6_23 Aleksei V. Fishkin. 2003. Disk graphs: A short survey. In Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16--18, 2003, Revised Papers (Lecture Notes in Computer Science), Klaus Jansen and Roberto Solis-Oba (Eds.), Vol. 2909. Springer, 260--264. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24592-6_23"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110403"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 18th European Symposium on Algorithms (ESA\u201910)","author":"Gibson Matt","unstructured":"Matt Gibson and Imran A. Pirwani . 2010. Algorithms for dominating set in disk graphs: Breaking the log n barrier\u2014(Extended abstract) . In Proceedings of the 18th European Symposium on Algorithms (ESA\u201910) . 243--254. DOI:https:\/\/doi.org\/10.1007\/978-3-642-15775-2_21 10.1007\/978-3-642-15775-2_21 Matt Gibson and Imran A. Pirwani. 2010. Algorithms for dominating set in disk graphs: Breaking the log n barrier\u2014(Extended abstract). In Proceedings of the 18th European Symposium on Algorithms (ESA\u201910). 243--254. DOI:https:\/\/doi.org\/10.1007\/978-3-642-15775-2_21"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00321-M"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918)","author":"Har-Peled Sariel","year":"2018","unstructured":"Sariel Har-Peled , Haim Kaplan , Wolfgang Mulzer , Liam Roditty , Paul Seiferth , Micha Sharir , and Max Willert . 2018 . Stabbing pairwise intersecting disks by five points . In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918) . 50:1--50:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.50 10.4230\/LIPIcs.ISAAC.2018.50 Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert. 2018. Stabbing pairwise intersecting disks by five points. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918). 50:1--50:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.50"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116257.3116364"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910)","author":"Reed Kawarabayashi","year":"1806","unstructured":"Ken-ichi Kawarabayashi and Bruce A. Reed . 2010. Odd cycle packing . In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910) . 695--704. DOI:https:\/\/doi.org\/10.1145\/ 1806 689.1806785 10.1145\/1806689.1806785 Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. Odd cycle packing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910). 695--704. DOI:https:\/\/doi.org\/10.1145\/1806689.1806785"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.148"},{"key":"e_1_2_1_44_1","first-page":"141","article-title":"Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhandlungen der S\u00e4chsischen Akademie der Wissenschaften zu Leipzig","volume":"88","author":"Koebe Paul","year":"1936","unstructured":"Paul Koebe . 1936 . Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhandlungen der S\u00e4chsischen Akademie der Wissenschaften zu Leipzig , Mathematisch-Physikalische Klasse 88 (1936), 141 -- 164 . Paul Koebe. 1936. Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhandlungen der S\u00e4chsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physikalische Klasse 88 (1936), 141--164.","journal-title":"Mathematisch-Physikalische Klasse"},{"key":"e_1_2_1_45_1","first-page":"139","article-title":"Precoloring extension with fixed color bound","volume":"62","author":"Kratochvil Jan","year":"1993","unstructured":"Jan Kratochvil . 1993 . Precoloring extension with fixed color bound . Acta Math. Univ. Comen 62 (1993), 139 -- 153 . Jan Kratochvil. 1993. Precoloring extension with fixed color bound. Acta Math. Univ. Comen 62 (1993), 139--153.","journal-title":"Acta Math. Univ. Comen"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the Symposium on Graph Drawing (GD\u201996)","author":"Kratochv\u00edl Jan","year":"1996","unstructured":"Jan Kratochv\u00edl . 1996 . Intersection graphs of noncrossing arc-connected sets in the plane . In Proceedings of the Symposium on Graph Drawing (GD\u201996) . 257--270. DOI:https:\/\/doi.org\/10.1007\/3-540-62495-3_53 10.1007\/3-540-62495-3_53 Jan Kratochv\u00edl. 1996. Intersection graphs of noncrossing arc-connected sets in the plane. In Proceedings of the Symposium on Graph Drawing (GD\u201996). 257--270. DOI:https:\/\/doi.org\/10.1007\/3-540-62495-3_53"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1071"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199808)32:1<13::AID-NET2>3.0.CO;2-M"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_50_1","volume-title":"McMorris","author":"McKee Terry A.","year":"1999","unstructured":"Terry A. McKee and Fred R . McMorris . 1999 . Topics in Intersection Graph Theory. SIAM. Terry A. McKee and Fred R. McMorris. 1999. Topics in Intersection Graph Theory. SIAM."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90688-C"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA\u201915)","author":"Nieberg Tim","year":"2005","unstructured":"Tim Nieberg and Johann Hurink . 2005 . A PTAS for the minimum dominating set problem in unit disk graphs . In Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA\u201915) . 296--306. DOI:https:\/\/doi.org\/10.1007\/11671411_23 10.1007\/11671411_23 Tim Nieberg and Johann Hurink. 2005. A PTAS for the minimum dominating set problem in unit disk graphs. In Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA\u201915). 296--306. DOI:https:\/\/doi.org\/10.1007\/11671411_23"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30559-0_18"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00048-8"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS\u201998)","author":"Warren","year":"1998","unstructured":"Warren D. Smith and Nicholas C. Wormald. 1998. Geometric separator theorems 8 applications . In Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS\u201998) . 232--243. DOI:https:\/\/doi.org\/10.1109\/SFCS. 1998 .743449 10.1109\/SFCS.1998.743449 Warren D. Smith and Nicholas C. Wormald. 1998. Geometric separator theorems 8 applications. In Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS\u201998). 232--243. DOI:https:\/\/doi.org\/10.1109\/SFCS.1998.743449"},{"key":"e_1_2_1_57_1","first-page":"1","article-title":"A solution of Gallai\u2019s problem on pinning down circles","volume":"32","author":"Stach\u00f3 Lajos","year":"1981","unstructured":"Lajos Stach\u00f3 . 1981 . A solution of Gallai\u2019s problem on pinning down circles . Mat. Lapok 32 , 1 \u2013 3 (1981), 19--47. Lajos Stach\u00f3. 1981. A solution of Gallai\u2019s problem on pinning down circles. Mat. Lapok 32, 1\u20133 (1981), 19--47.","journal-title":"Mat. Lapok"},{"key":"e_1_2_1_58_1","first-page":"270","article-title":"Some elementary properties of closed plane curves","volume":"69","author":"Tait Peter Guthrie","year":"1877","unstructured":"Peter Guthrie Tait . 1877 . Some elementary properties of closed plane curves . Mess. Math., New Series 69 (1877), 270 -- 272 . Peter Guthrie Tait. 1877. Some elementary properties of closed plane curves. Mess. Math., New Series 69 (1877), 270--272.","journal-title":"Mess. Math., New Series"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_30"},{"key":"e_1_2_1_61_1","volume-title":"Meas. Complex","author":"Vapnik Vladimir N.","unstructured":"Vladimir N. Vapnik and A. Ya Chervonenkis . 2015. On the uniform convergence of relative frequencies of events to their probabilities . In Meas. Complex . Springer , 11--30. Vladimir N. Vapnik and A. Ya Chervonenkis. 2015. On the uniform convergence of relative frequencies of events to their probabilities. In Meas. Complex. Springer, 11--30."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3433160","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3433160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:10Z","timestamp":1750193290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3433160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,6]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3433160"],"URL":"https:\/\/doi.org\/10.1145\/3433160","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,6]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}