EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Publication:5056440
DOI10.1145/3433160zbMath1499.68256arXiv2110.15419MaRDI QIDQ5056440
Eun Jung Kim, Marthe Bonamy, Paweł Rzążewski, Pierre Charbit, Édouard Bonnet, Florian Sikora, Panos Giannopoulos, Steéphan Thomassé, Nicolas Bousquet
Publication date: 8 December 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.15419
computational complexity; approximation algorithms; maximum clique; disk graph; subexponential algorithms
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items