City Research Online

Abstract

A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n7/3+o(1)), where n denotes the number of disks [19, 28]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O∗(n2t) [28]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization:

(i) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1 − ε)-approximate maximum clique in expected time O˜(n/ε2); and

(ii) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1 − ε)-approximate maximum clique in expected time O˜(f(t) · (1/ε) O(t)· n), for some (exponential) function f(t).

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	© Jie Gao, Pawel Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals and Meirav Zehavi; licensed under Creative Commons License CC-BY 4.0
Publisher Keywords:	Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation
Subjects:	Q Science > QA Mathematics
Departments:	School of Science & Technology School of Science & Technology > Department of Computer Science School of Science & Technology > Department of Computer Science > giCentre
SWORD Depositor:	Symplectic Administrator

Export

Downloads