Mostrar el registro sencillo del ítem
dc.contributor.author
Lin, Min Chih
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Mizrahi, Michel Jonathan
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2018-09-13T18:53:14Z
dc.date.issued
2015-12
dc.identifier.citation
Lin, Min Chih; Mizrahi, Michel Jonathan; On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size; Elsevier Science; Discrete Applied Mathematics; 197; 12-2015; 53-58
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/59587
dc.description.abstract
We study the computational complexity of the minimum dominating set problem on graphs restricted by forbidden induced subgraphs. We give some dichotomies results for the problem on graphs defined by any combination of forbidden induced subgraphs with at most four vertices, implying either an NP-Hardness proof or a polynomial time algorithm. We also extend the results by showing that dominating set problem remains NP-hard even when the graph has maximum degree three, it is planar and has no induced claw, induced diamond, induced K4 nor induced cycle of length 4, 5, 7, 8, 9, 10 and 11.
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-nd/2.5/ar/
dc.subject
Algorithms
dc.subject
Complexity
dc.subject
Dominating Set
dc.subject
Forbidden Induced Subgraphs
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![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
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
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
2018-09-13T13:12:31Z
dc.journal.volume
197
dc.journal.pagination
53-58
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: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Mizrahi, Michel Jonathan. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.journal.title
Discrete Applied Mathematics
![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.dam.2015.02.010
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X15000967
Archivos asociados