On PTAS for planar graph problems

Approximation algorithms for a class of planar graph problems, including planar independent set, planar vertex cover and planar 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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Huang, Xiuzhen, Chen, Jianer
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Informáticas
vertex
polynomial time approximation schemes (PTAS)
Graph algorithms
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24423
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-24423
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
vertex
polynomial time approximation schemes (PTAS)
Graph algorithms
spellingShingle Ciencias Informáticas
vertex
polynomial time approximation schemes (PTAS)
Graph algorithms
Huang, Xiuzhen
Chen, Jianer
On PTAS for planar graph problems
topic_facet Ciencias Informáticas
vertex
polynomial time approximation schemes (PTAS)
Graph algorithms
description Approximation algorithms for a class of planar graph problems, including planar independent set, planar vertex cover and planar 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 2<sup>O(1/∈ )</sup>n<sup>O(1)</sup>. 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 2<sup>=(√(1/∈ )</sup>n<sup>O(1)</sup> 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 speci cally 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 pla- nar graphs of degree bounded by three.
format Objeto de conferencia
Objeto de conferencia
author Huang, Xiuzhen
Chen, Jianer
author_facet Huang, Xiuzhen
Chen, Jianer
author_sort Huang, Xiuzhen
title On PTAS for planar graph problems
title_short On PTAS for planar graph problems
title_full On PTAS for planar graph problems
title_fullStr On PTAS for planar graph problems
title_full_unstemmed On PTAS for planar graph problems
title_sort on ptas for planar graph problems
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/24423
work_keys_str_mv AT huangxiuzhen onptasforplanargraphproblems
AT chenjianer onptasforplanargraphproblems
bdutipo_str Repositorios
_version_ 1764820466046861314

Ejemplares similares