Cycle transversals in bounded degree graphs

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-trans...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Groshaus, Marina E.
Publicado: 2009
Materias:
H-free graph
H-subgraph
H-transversal
transversal
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p189_Groshaus
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p189_Groshaus
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v35_nC_p189_Groshaus
record_format dspace
spelling paper:paper_15710653_v35_nC_p189_Groshaus2023-06-08T16:24:24Z Cycle transversals in bounded degree graphs Groshaus, Marina E. H-free graph H-subgraph H-transversal transversal 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. © 2009 Elsevier B.V. All rights reserved. Fil:Groshaus, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p189_Groshaus http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p189_Groshaus
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic H-free graph
H-subgraph
H-transversal
transversal
spellingShingle H-free graph
H-subgraph
H-transversal
transversal
Groshaus, Marina E.
Cycle transversals in bounded degree graphs
topic_facet H-free graph
H-subgraph
H-transversal
transversal
description 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. © 2009 Elsevier B.V. All rights reserved.
author Groshaus, Marina E.
author_facet Groshaus, Marina E.
author_sort Groshaus, Marina E.
title Cycle transversals in bounded degree graphs
title_short Cycle transversals in bounded degree graphs
title_full Cycle transversals in bounded degree graphs
title_fullStr Cycle transversals in bounded degree graphs
title_full_unstemmed Cycle transversals in bounded degree graphs
title_sort cycle transversals in bounded degree graphs
publishDate 2009
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p189_Groshaus
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p189_Groshaus
work_keys_str_mv AT groshausmarinae cycletransversalsinboundeddegreegraphs
_version_ 1768546647111892992

Ejemplares similares