Total 2-domination of proper interval graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación | |
| dc.contributor.author | Soulignac, Francisco Juan | |
| dc.date.issued | 2021-10 | |
| dc.description.abstract | A set of vertices W of a graph G is a total k-dominating set when every vertex of G has at least k neighbors in W. In a recent article, Chiarelli et al. (2019) prove that a total k-dominating set can be computed in O(n3k) time when G is a proper interval graph with n vertices and m edges. In this note we reduce the time complexity to O(m) for k=2. | es |
| dc.description.fil | Fil: Soulignac, Francisco Juan. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Soulignac, Francisco Juan; Total 2-domination of proper interval graphs; Elsevier Science; Discrete Applied Mathematics; 302; 10-2021; 256-262 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/173291 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 256-262 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 302 | 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.2021.07.015 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1812.00689?context=math.CO#:~:text=A%20set%20of%20vertices%20W,Graphs%2C%20Lecture%20Notes%20in%20Comput. | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | PROPER INTERVAL GRAPHS | es |
| dc.subject | STRAIGHT ORIENTED GRAPHS | es |
| dc.subject | TOTAL 2-DOMINATION | 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 | Total 2-domination of 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.4d5e6ac3-55db-4614-ad9b-8ef5302cb16f_B.pdf
- Tamaño:
- 200.57 KB
- Formato:
- Adobe Portable Document Format