Mostrar el registro sencillo del ítem
dc.contributor.author
Dobson, M. P.
dc.contributor.author
Hinrichsen, E.
dc.contributor.author
Leoni, Valeria Alejandra
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2017-02-23T20:47:45Z
dc.date.issued
2015-05
dc.identifier.citation
Dobson, M. P.; Hinrichsen, E.; Leoni, Valeria Alejandra; Generalized limited packings of some graphs with a limited number of P4-partners; Elsevier Science; Theoretical Computer Science; 579; 5-2015; 1-8
dc.identifier.issn
0304-3975
dc.identifier.uri
http://hdl.handle.net/11336/13338
dc.description.abstract
By using modular decomposition and handling certain graph operations such as join and union, we show that the Generalized Limited Packing Problem—NP-complete in general—can be solved in polynomial time in some graph classes with a limited number of P4-partners; specifically P4-tidy graphs, which contain cographs and P4-sparse graphs. In particular, we describe an algorithm to compute the associated numbers in polynomial time within these graph classes. In this way, we generalize some of the previous results on the subject. We also make some progress on the study of the computational complexity of the Generalized Multiple Domination Problem in graphs.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Generalized Limited Packing
dc.subject
Join
dc.subject
Union
dc.subject
P4-Partners
dc.subject.classification
Otras Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Generalized limited packings of some graphs with a limited number of P4-partners
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
2017-02-23T13:54:46Z
dc.journal.volume
579
dc.journal.pagination
1-8
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Dobson, M. P.. Universidad Nacional de Rosario. Facultad de Cs.exactas Ingenieria y Agrimensura. Escuela de Cs.exactas y Naturales. Departamento de Matematica; Argentina
dc.description.fil
Fil: Hinrichsen, E.. Universidad Nacional de Rosario. Facultad de Cs.exactas Ingenieria y Agrimensura. Escuela de Cs.exactas y Naturales. Departamento de Matematica; Argentina
dc.description.fil
Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Cs.exactas Ingenieria y Agrimensura. Escuela de Cs.exactas y Naturales. Departamento de Matematica; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Cientifico Tecnológico Rosario; Argentina
dc.journal.title
Theoretical Computer Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2014.11.014
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0304397514008573
Archivos asociados