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

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

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

Related Items

Faster 3-Coloring of Small-Diameter Graphs, Computing list homomorphisms in geometric intersection graphs, Induced odd cycle packing number, independent sets, and chromatic number