Mostrar el registro sencillo del ítem

dc.contributor.author
Yekezare, N.  
dc.contributor.author
Zohrehbandian, M.  
dc.contributor.author
Maghasedi, M.  
dc.contributor.author
Bonomo, Flavia  
dc.date.available
2025-04-14T14:12:32Z  
dc.date.issued
2024-09  
dc.identifier.citation
Yekezare, N.; Zohrehbandian, M.; Maghasedi, M.; Bonomo, Flavia; Optimality of DSatur algorithm on chordal graphs; Elsevier Science; Operations Research Letters; 57; 9-2024; 1-5  
dc.identifier.issn
0167-6377  
dc.identifier.uri
http://hdl.handle.net/11336/258715  
dc.description.abstract
DSatur is a widely-used heuristic algorithm for graph coloring, proposed by Daniel Brélaz in 1979. It is based on the greedy coloring approach, but selecting the next vertex to be colored from those that maximize the number of colors already used by their neighbors. Though not always optimal, this algorithm is known to be optimal on certain families, like cycles or bipartite graphs. In this paper, we prove the optimality of DSatur on chordal graphs, a superclass of interval graphs.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/restrictedAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
DSatur Algorithm  
dc.subject
Chordal Graphs  
dc.subject
Vertex Coloring Problem  
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.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Optimality of DSatur algorithm on chordal 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
2025-04-14T10:36:03Z  
dc.journal.volume
57  
dc.journal.pagination
1-5  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Yekezare, N.. Islamic Azad University; Irán  
dc.description.fil
Fil: Zohrehbandian, M.. Islamic Azad University; Irán  
dc.description.fil
Fil: Maghasedi, M.. Islamic Azad University; Irán  
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.journal.title
Operations Research Letters  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.orl.2024.107185  

Archivos asociados
Tamaño: 467.4Kb
Formato: PDF
.