Artículo

Cycle transversals in bounded degree graphs

Groshaus, Marina EstherIcon ; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F.
Fecha de publicación: 12/2009
Editorial: Elsevier
Revista: Electronic Notes in Discrete Mathematics
ISSN: 1365-8050
e-ISSN: 1571-0653
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

In this work we consider the problem of finding a minimum Ck-transversal (a subset of vertices hitting all the induced chordless cycles with k vertices) in a graph with bounded maximum degree. In particular, we seek for dichotomy results as follows: for a fixed value of k, finding a minimum Ck-transversal is polynomial-time solvable if k ≤ p, and NP-hard otherwise.
Palabras clave: H-Free Graph , H-Subgraph , H-Transversal , Transversal
 
Archivos asociados
Thumbnail
 
Tamaño: 562.4Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution 2.5 Unported (CC BY 2.5)
Identificadores
URI: http://hdl.handle.net/11336/68193
URL: https://www.sciencedirect.com/science/article/pii/S1571065309001851
DOI: https://doi.org/10.1016/j.endm.2009.11.032
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Groshaus, Marina Esther; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F.; Cycle transversals in bounded degree graphs; Elsevier; Electronic Notes in Discrete Mathematics; 35; C; 12-2009; 189-195
Compartir
Altmétricas