Subir material

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2020-04-29T14:59:55Z
dc.date.available 2020-04-29T14:59:55Z
dc.date.issued 2013
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/94545
dc.description.abstract In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with k-DOM, we prove that {k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second- order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. In this way we enlarge the family of graphs for which k-DOM is polynomial time solvable. en
dc.format.extent 4 es
dc.language en es
dc.subject Chordal graphs es
dc.subject k-DOM es
dc.title On the Complexity of {k}-domination for Chordal Graphs en
dc.type Objeto de conferencia es
sedici.identifier.issn 1850-2865 es
sedici.creator.person Argiroffo, G. es
sedici.creator.person Leoni, V. es
sedici.creator.person Torres, P. es
sedici.subject.materias Ciencias Informáticas es
sedici.description.fulltext true es
mods.originInfo.place Sociedad Argentina de Informática e Investigación Operativa es
sedici.subtype Resumen es
sedici.rights.license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-sa/4.0/
sedici.date.exposure 2013-09
sedici.relation.event XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) es
sedici.description.peerReview peer-review es


Descargar archivos

Thumbnail
Resumen
Descargar archivo (211.5Kb) - PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)