{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:09Z","timestamp":1740122409270,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["SNSF Project 200021E-171681"],"award-info":[{"award-number":["SNSF Project 200021E-171681"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the 90\u2019s Clark, Colbourn and Johnson wrote a seminal paper where they proved that maximum clique can be solved in polynomial time in unit disk graphs. Since then, the complexity of maximum clique in intersection graphs of <jats:italic>d<\/jats:italic>-dimensional (unit) balls has been investigated. For ball graphs, the problem is NP-hard, as shown by Bonamy et al. (FOCS\u00a0\u201918). They also gave an efficient polynomial time approximation scheme (EPTAS) for disk graphs. However, the complexity of maximum clique in this setting remains unknown. In this paper, we show the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs. Moreover, we give partial results toward obtaining an EPTAS for intersection graphs of convex pseudo-disks.<\/jats:p>","DOI":"10.1007\/s10878-022-00853-2","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T19:03:33Z","timestamp":1648235013000},"page":"3106-3135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing a maximum clique in geometric superclasses of disk graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Nicolas","family":"Grelier","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"key":"853_CR1","unstructured":"Aronov B, Donakonda, Anirudh EE, Pinchasi R (2018) On pseudo-disk hypergraphs. arXiv:1802.08799,"},{"issue":"5","key":"853_CR2","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy A, Bar-Yehuda R, Freund A, Naor J, Schieber B (2001) A unified approach to approximating resource allocation and scheduling. J ACM (JACM) 48(5):1069\u20131090","journal-title":"J ACM (JACM)"},{"key":"853_CR3","doi-asserted-by":"crossref","unstructured":"Bonamy M, Bonnet \u00c9, Bousquet N, Charbit P, Thomass\u00e9 S (2018) EPTAS for max clique on disks and unit balls. In: 2018 IEEE 59th annual symposium on foundations of computer science (FOCS). IEEE, pp 568\u2013579","DOI":"10.1109\/FOCS.2018.00060"},{"key":"853_CR4","unstructured":"Bonnet \u00c9, Giannopoulos P, Kim EJ, Rz\u0105\u017cewski P, Sikora F (2018) QPTAS and subexponential algorithm for maximum clique on disk graphs. In: 34th international symposiumon computational geometry (SoCG), pp. 12:1\u201312:15"},{"key":"853_CR5","unstructured":"Bonnet \u00c9, Grelier N, Miltzow T (2020) Maximum clique in disk-like intersection graphs. arXiv:2003.02583"},{"issue":"1\u20133","key":"853_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discret Math 86(1\u20133):165\u2013177","journal-title":"Discret Math"},{"key":"853_CR7","unstructured":"Dvo\u0159\u00e1k Z, Pek\u00e1rek J (2020) Induced odd cycle packing number, independent sets, and chromatic number. arXiv:2001.02411"},{"issue":"2","key":"853_CR8","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J ACM (JACM) 19(2):248\u2013264","journal-title":"J ACM (JACM)"},{"key":"853_CR9","doi-asserted-by":"crossref","unstructured":"Fishkin AV (2003) Disk graphs: a short survey. In: International workshop on approximation and online algorithms. Springer, pp 260\u2013264","DOI":"10.1007\/978-3-540-24592-6_23"},{"key":"853_CR10","doi-asserted-by":"crossref","unstructured":"Grelier N (2020) Computing a maximum clique in geometric superclasses of disk graphs. In: International computing and combinatorics conference. Springer, pp 299\u2013310","DOI":"10.1007\/978-3-030-58150-3_24"},{"issue":"4","key":"853_CR11","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"UI Gupta","year":"1982","unstructured":"Gupta UI, Lee D-T, Leung JY-T (1982) Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4):459\u2013467","journal-title":"Networks"},{"issue":"4","key":"853_CR12","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H Imai","year":"1983","unstructured":"Imai H, Asano T (1983) Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J Algorithms 4(4):310\u2013323","journal-title":"J Algorithms"},{"issue":"3","key":"853_CR13","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"RJ Kang","year":"2012","unstructured":"Kang RJ, M\u00fcller T (2012) Sphere and dot product representations of graphs. Discrete Comput Geom 47(3):548\u2013568","journal-title":"Discrete Comput Geom"},{"key":"853_CR14","unstructured":"Raghavan V, Spinrad J (2001) Robust algorithms for restricted domains. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp 460\u2013467"},{"key":"853_CR15","unstructured":"van Leeuwen EJ (2009) Optimization and approximation on systems of geometric objects. Universiteit van Amsterdam [Host]"},{"key":"853_CR16","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik VN, Ya Chervonenkis A (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab Appl 16:264\u2013280","journal-title":"Theory Probab Appl"},{"key":"853_CR17","unstructured":"Wenger R, Holmsen A (2017) Helly-type theorems and geometric transversals. In: Handbook of discrete and computational geometry, 3d edn. Chapman and Hall\/CRC, pp 91\u2013123"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00853-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00853-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00853-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:26:26Z","timestamp":1665779186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00853-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,25]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["853"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00853-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,3,25]]},"assertion":[{"value":"28 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data availability"}},{"value":"The author declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}