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
Autores principales: Groshaus, M., Hell, P., Klein, S., Nogueira, L.T., Protti, F.
Formato: JOUR
Materias:
H-free graph
H-subgraph
H-transversal
transversal
Acceso en línea: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 todo:paper_15710653_v35_nC_p189_Groshaus
record_format dspace
spelling todo:paper_15710653_v35_nC_p189_Groshaus2023-10-03T16:27:03Z Cycle transversals in bounded degree graphs Groshaus, M. Hell, P. Klein, S. Nogueira, L.T. Protti, F. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.
Hell, P.
Klein, S.
Nogueira, L.T.
Protti, F.
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.
format JOUR
author Groshaus, M.
Hell, P.
Klein, S.
Nogueira, L.T.
Protti, F.
author_facet Groshaus, M.
Hell, P.
Klein, S.
Nogueira, L.T.
Protti, F.
author_sort Groshaus, M.
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
url http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p189_Groshaus
work_keys_str_mv AT groshausm cycletransversalsinboundeddegreegraphs
AT hellp cycletransversalsinboundeddegreegraphs
AT kleins cycletransversalsinboundeddegreegraphs
AT nogueiralt cycletransversalsinboundeddegreegraphs
AT prottif cycletransversalsinboundeddegreegraphs
_version_ 1807323372747489280

Ejemplares similares