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

DOI10.1145/3433160zbMath1499.68256arXiv2110.15419OpenAlexW3210983782MaRDI 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 complexityapproximation algorithmsmaximum cliquedisk graphsubexponential algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

Computing list homomorphisms in geometric intersection graphs ⋮ Induced odd cycle packing number, independent sets, and chromatic number ⋮ Faster algorithms for cycle hitting problems on disk graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs

This page was built for publication: EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs