{k}-domination for chordal graphs and related graph classes | ||
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.contributor.author | Argiroffo, Gabriela Rut | |
| dc.contributor.author | Leoni, Valeria Alejandra | |
| dc.contributor.author | Torres, Pablo Daniel | |
| dc.date.issued | 2013-11 | |
| dc.description.abstract | In this work we obtain a new graph class where the {. k}-dominating function problem ({. k}-DOM) is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. Firstly, by relating this problem with the k-dominating function problem (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. Finally, we show that {. k}-DOM is linear time solvable for spider graphs. | es |
| dc.description.fil | Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina | |
| dc.description.fil | Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Torres, Pablo Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Argiroffo, Gabriela Rut; Leoni, Valeria Alejandra; Torres, Pablo Daniel; {k}-domination for chordal graphs and related graph classes; Elsevier; Electronic Notes in Discrete Mathematics; 44; 11-2013; 219-224 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 1571-0653 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/94349 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 219-224 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Electronic Notes in Discrete Mathematics | es |
| dc.journal.volume | 44 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.endm.2013.10.034 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065313002503 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | CHORDAL GRAPH | es |
| dc.subject | COMPUTATIONAL COMPLEXITY | es |
| dc.subject | K-DOMINATING FUNCTION | es |
| dc.subject | {K}-DOMINATING FUNCTION | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | {k}-domination for chordal graphs and related graph classes | 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.0142d351-b1c8-446f-bb01-a1aca27f7fa1_A.pdf
- Tamaño:
- 184.82 KB
- Formato:
- Adobe Portable Document Format