Mostrar el registro sencillo del ítem

dc.contributor.author
Lin, Min Chih  
dc.contributor.author
Mizrahi, Michel Jonathan  
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  
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  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
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  
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  
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
Thumbnail
 
Tamaño: 392.2Kb
Formato: PDF
.