Cycle transversals in bounded degree graphs

dc.creatorGroshaus, Marina Esther
dc.creatorHell, P.
dc.creatorKlein, S.
dc.creatorNogueira, L. T.
dc.creatorProtti, F.
dc.date.accessioned2019-01-17T17:52:39Z
dc.date.accessioned2022-10-15T08:11:41Z
dc.date.available2019-01-17T17:52:39Z
dc.date.available2022-10-15T08:11:41Z
dc.date.created2019-01-17T17:52:39Z
dc.date.issued2009-12
dc.identifierGroshaus, 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
dc.identifier1365-8050
dc.identifierhttp://hdl.handle.net/11336/68193
dc.identifier1571-0653
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/4363769
dc.description.abstractIn 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.
dc.languageeng
dc.publisherElsevier
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065309001851
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.endm.2009.11.032
dc.rightshttps://creativecommons.org/licenses/by/2.5/ar/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectH-Free Graph
dc.subjectH-Subgraph
dc.subjectH-Transversal
dc.subjectTransversal
dc.titleCycle transversals in bounded degree graphs
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución