On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Lin, Min Chih | |
| dc.contributor.author | Mizrahi, Michel Jonathan | |
| dc.date.issued | 2015-12 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/59587 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 53-58 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 197 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| 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 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Algorithms | es |
| dc.subject | Complexity | es |
| dc.subject | Dominating Set | es |
| dc.subject | Forbidden Induced Subgraphs | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.e9e52791-85b0-414c-b5eb-ac37af5cf945_A.pdf
- Tamaño:
- 392.29 KB
- Formato:
- Adobe Portable Document Format