Mostrar el registro sencillo del ítem

dc.contributor.author
Groshaus, Marina Esther  
dc.contributor.author
Hell, P.  
dc.contributor.author
Klein, S.  
dc.contributor.author
Nogueira, L. T.  
dc.contributor.author
Protti, F.  
dc.date.available
2019-01-17T17:52:39Z  
dc.date.issued
2009-12  
dc.identifier.citation
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  
dc.identifier.issn
1365-8050  
dc.identifier.uri
http://hdl.handle.net/11336/68193  
dc.description.abstract
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by/2.5/ar/  
dc.subject
H-Free Graph  
dc.subject
H-Subgraph  
dc.subject
H-Transversal  
dc.subject
Transversal  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Cycle transversals in bounded degree graphs  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2019-01-14T17:58:23Z  
dc.identifier.eissn
1571-0653  
dc.journal.volume
35  
dc.journal.number
C  
dc.journal.pagination
189-195  
dc.journal.pais
Francia  
dc.description.fil
Fil: Groshaus, Marina Esther. Universidad de Buenos Aires; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria; Argentina  
dc.description.fil
Fil: Hell, P.. University Fraser Simon; Canadá  
dc.description.fil
Fil: Klein, S.. Universidade Federal do Rio de Janeiro; Brasil  
dc.description.fil
Fil: Nogueira, L. T.. Universidade Federal Fluminense; Brasil  
dc.description.fil
Fil: Protti, F.. Universidade Federal Fluminense; Brasil. Universidade Federal do Rio de Janeiro; Brasil  
dc.journal.title
Electronic Notes in Discrete Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065309001851  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.endm.2009.11.032  

Archivos asociados
Thumbnail
 
Tamaño: 562.4Kb
Formato: PDF
.