New algorithms for weighted k-domination and total k-domination problems in proper interval graphs | ||
| dc.conicet.organizacion | Univerza Na Primorskem. Faculty of Mathematics, Natural Sciences and Information Technologies | |
| dc.conicet.organizacion | Cognitiva Etermax Labs | |
| 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.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Ministerio de Ciencia. Tecnología e Innovación Productiva. Agencia Nacional de Promoción Científica y Tecnológica | |
| dc.conicet.organizacion | Univerza Na Primorskem. Faculty of Mathematics, Natural Sciences and Information Technologies | |
| dc.contributor.author | Chiarelli, Nina | |
| dc.contributor.author | Hartinger, Tatiana Romina | |
| dc.contributor.author | Leoni, Valeria Alejandra | |
| dc.contributor.author | Lopez Pujato, María Inés | |
| dc.contributor.author | Milanič, Martin | |
| dc.date.issued | 2019-11 | |
| dc.description.abstract | Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, respectively total k-dominating set, in a given graph, are referred to as k-domination, respectively total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from previous works by Bui-Xuan et al. (2013) [8] and by Belmonte and Vatshelle (2013) [3] that these two families of problems are solvable in time O(|V(G)|3k+4) in the class of interval graphs. We develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs, by means of reduction to a single shortest path computation in a derived directed acyclic graph with O(|V(G)|2k) nodes and O(|V(G)|4k) arcs. We show that a suitable implementation, which avoids constructing all arcs of the digraph, leads to a running time of O(|V(G)|3k). The algorithms are also applicable to the weighted case. | es |
| dc.description.fil | Fil: Chiarelli, Nina. Univerza Na Primorskem. Faculty of Mathematics, Natural Sciences and Information Technologies; Eslovenia | |
| dc.description.fil | Fil: Hartinger, Tatiana Romina. Cognitiva Etermax Labs; Estados Unidos | |
| dc.description.fil | Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina | |
| dc.description.fil | Fil: Lopez Pujato, María Inés. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Ministerio de Ciencia. Tecnología e Innovación Productiva. Agencia Nacional de Promoción Científica y Tecnológica; Argentina | |
| dc.description.fil | Fil: Milanič, Martin. Univerza Na Primorskem. Faculty of Mathematics, Natural Sciences and Information Technologies; Eslovenia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Chiarelli, Nina; Hartinger, Tatiana Romina; Leoni, Valeria Alejandra; Lopez Pujato, María Inés; Milanič, Martin; New algorithms for weighted k-domination and total k-domination problems in proper interval graphs; Elsevier Science; Theoretical Computer Science; 795; 11-2019; 128-141 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0304-3975 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/127689 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 128-141 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Theoretical Computer Science | es |
| dc.journal.volume | 795 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0304397519303937 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2019.06.007 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1803.04327 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | K-DOMINATION | es |
| dc.subject | POLYNOMIAL-TIME ALGORITHM | es |
| dc.subject | PROPER INTERVAL GRAPH | es |
| dc.subject | TOTAL K-DOMINATION | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | New algorithms for weighted k-domination and total k-domination problems in proper interval graphs | 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.bb7e968b-2170-4a5e-812c-d3c371a0882a_X.pdf
- Tamaño:
- 521.66 KB
- Formato:
- Adobe Portable Document Format
- Descripción: