Geometric separation and exact solutions for the parameterized independent set problem on disk graphs |
| |
Authors: | Jochen Alber Jií Fiala |
| |
Institution: | aWilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany;bCharles University, Faculty of Mathematics and Physics, Department of Applied Mathematics, DIMATIA and Institute for Theoretical Computer Science (ITI),3 Malostranské nám. 2/25, 118 00 Prague, Czech Republic |
| |
Abstract: | We consider the parameterized problem, whether for a given set
of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time
that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time
. The results are based on problem kernelization and a new “geometric (
-separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.” |
| |
Keywords: | Disk graphs Independent set Parameterized complexity Graph separators Graph measure |
本文献已被 ScienceDirect 等数据库收录! |
|