Mostrar el registro sencillo del ítem

dc.contributor.author
Soulignac, Francisco Juan  
dc.date.available
2022-10-14T16:51:00Z  
dc.date.issued
2021-10  
dc.identifier.citation
Soulignac, Francisco Juan; Total 2-domination of proper interval graphs; Elsevier Science; Discrete Applied Mathematics; 302; 10-2021; 256-262  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/173291  
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.  
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-sa/2.5/ar/  
dc.subject
PROPER INTERVAL GRAPHS  
dc.subject
STRAIGHT ORIENTED GRAPHS  
dc.subject
TOTAL 2-DOMINATION  
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
Total 2-domination of proper interval graphs  
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
2022-09-22T16:15:44Z  
dc.journal.volume
302  
dc.journal.pagination
256-262  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
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.journal.title
Discrete Applied Mathematics  
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.  

Archivos asociados
Thumbnail
 
Tamaño: 200.5Kb
Formato: PDF
.