On PTAS for Planar Graph Problems Academic Article

abstract

• Approximation algorithms for a class of planar graph problems, including Planar Independent Set, Planar Vertex Cover and Poanar Dominating Set, were intensively studied. The current upper bound on the running time of the polynomial time approximation schemes (PTAS) for these planar graph problems is of 2O(1/)nO(1). Here we study the lower bound on the running time of the PTAS for these planar graph problems. We prove that there is no PTAS of time 2o(1/)nO(1) for Planar Independent Set, Planar Vertex Cover and Planar Dominating Set unless an unlikely collapse occurs in parameterized complexity theory. For the gap between our lower bound and the current known upper bound, we specifically show that to further improve the upper bound on the running time of the PTAS for PLANAR Vertex Cover, we can concentrate on Planar Vertex Cover on planar graphs of degree bounded by three. 2006 International Federation for Information Processing.

authors

• Chen, Jianer

published proceedings

• IFIP International Federation for Information Processing

author list (cited authors)

• Huang, X., & Chen, J.

citation count

• 1

complete list of authors

• Huang, Xiuzhen||Chen, Jianer

publication date

• January 2006

publisher

• Springer Nature  Publisher

published in

• IFIP Advances in Information and Communication Technology  Journal

keywords

• Pediatric

Digital Object Identifier (DOI)

• 10.1007/978-0-387-34735-6_24

start page

• 299

end page

• 313

volume

• 209

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-0-387-34735-6_24