EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

DOI10.1145/3433160zbMath1499.68256arXiv2110.15419MaRDI QIDQ5056440

Panos Giannopoulos, Marthe Bonamy, Édouard Bonnet, Paweł Rzążewski, Florian Sikora, Pierre Charbit, Nicolas Bousquet, Eun Jung Kim, Steéphan Thomassé

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

zbMATH Keywords

computational complexity; approximation algorithms; maximum clique; disk graph; subexponential algorithms

Mathematics Subject Classification ID

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.)