Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Valencia Pabon, Mario  
dc.date.available
2017-06-23T19:13:34Z  
dc.date.issued
2014-03  
dc.identifier.citation
Bonomo, Flavia; Valencia Pabon, Mario; On the Minimum Sum Coloring of P4-sparse graphs; Springer Tokyo; Graphs And Combinatorics; 30; 2; 3-2014; 303-314  
dc.identifier.issn
0911-0119  
dc.identifier.uri
http://hdl.handle.net/11336/18782  
dc.description.abstract
In this paper, we study the Minimum Sum Coloring (MSC) problem on P4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P4-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P4-sparse graphs.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Springer Tokyo  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
Graph Coloring  
dc.subject
Minimum Sum Coloring  
dc.subject
P4-Sparse Graphs  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
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
On the Minimum Sum Coloring of P4-sparse 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
2017-06-23T14:10:53Z  
dc.identifier.eissn
1435-5914  
dc.journal.volume
30  
dc.journal.number
2  
dc.journal.pagination
303-314  
dc.journal.pais
Japón  
dc.journal.ciudad
Tokyo  
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. Santalo". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santalo"; Argentina  
dc.description.fil
Fil: Valencia Pabon, Mario. Universite de Paris 13-Nord; Francia  
dc.journal.title
Graphs And Combinatorics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s00373-012-1269-5  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00373-012-1269-5  

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