On the Minimum Sum Coloring of P4-sparse graphs

dc.creatorBonomo, Flavia
dc.creatorValencia Pabon, Mario
dc.date.accessioned2017-06-23T19:13:34Z
dc.date.accessioned2018-11-06T12:01:13Z
dc.date.available2017-06-23T19:13:34Z
dc.date.available2018-11-06T12:01:13Z
dc.date.created2017-06-23T19:13:34Z
dc.date.issued2014-03
dc.identifierBonomo, 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.identifier0911-0119
dc.identifierhttp://hdl.handle.net/11336/18782
dc.identifier1435-5914
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1862323
dc.description.abstractIn 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.languageeng
dc.publisherSpringer Tokyo
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s00373-012-1269-5
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00373-012-1269-5
dc.rightshttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectGraph coloring
dc.subjectMinimum Sum Coloring
dc.subjectP4-sparse graphs
dc.titleOn the Minimum Sum Coloring of P4-sparse graphs
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución