Journal Title
Title of Journal: Graphs and Combinatorics
|
Abbravation: Graphs and Combinatorics
|
|
|
|
|
|
|
|
Authors: Adrian Dumitrescu János Pach
Publish Date: 2011/03/17
Volume: 27, Issue: 3, Pages: 399-411
Abstract
The minimum clique partition MCP problem is that of partitioning the vertex set of a given graph into a minimum number of cliques Given n points in the plane the corresponding unit disk graph UDG has these points as vertices and edges connecting points at distance at most 1 MCP in UDGs is known to be NPhard and several constant factor approximations are known including a recent PTAS We present two improved approximation algorithms for MCP in UDGs with a realization I A polynomial time approximation scheme PTAS running in time nO1/varepsilon2 This improves on a previous PTAS with nO1/varepsilon4 running time by Pirwani and Salavatipour arXiv09042203v1 2009 II A randomized quadratictime algorithm with approximation ratio 216 This improves on a ratio 3 algorithm with On 2 running time by Cerioli et al Electron Notes Discret Math 1873–79 2004A Dumitrescu was supported in part by NSF CAREER grant CCF0444188 Part of the research by this author was done at Ecole Polytechnique Fédérale de Lausanne Research by J Pach was partially supported by NSF grant CCF0830272 Swiss National Science Foundation Grant 200021125287/1 by OTKA BSF and by the Bernoulli Center at EPFL
Keywords:
.
|
Other Papers In This Journal:
|