A note on the Cornaz-Jost transformation to solve the graph coloring problem

dc.creatorBonomo, Flavia
dc.creatorGiandomenico, Monia
dc.creatorRossi, Fabrizio
dc.date.accessioned2015-06-15T16:07:06Z
dc.date.accessioned2018-11-06T14:42:43Z
dc.date.available2015-06-15T16:07:06Z
dc.date.available2018-11-06T14:42:43Z
dc.date.created2015-06-15T16:07:06Z
dc.date.issued2013-06-04
dc.identifierBonomo, Flavia; Giandomenico, Monia; Rossi, Fabrizio; A note on the Cornaz-Jost transformation to solve the graph coloring problem; Elsevier Science Bv; Information Processing Letters; 113; 4-6-2013; 649-652
dc.identifier0020-0190
dc.identifierhttp://hdl.handle.net/11336/733
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1889319
dc.description.abstractIn this note, we use a reduction by Cornaz and Jost from the graph (max-)coloring problem to the maximum (weighted) stable set problem in order to characterize new graph classes where the graph coloring problem and the more general max-coloring problem can be solved in polynomial time.
dc.languageeng
dc.publisherElsevier Science Bv
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0020019013001567#
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://ac.els-cdn.com/S0020019013001567/1-s2.0-S0020019013001567-main.pdf?_tid=423cda20-1373-11e5-8380-00000aab0f6b&acdnat=1434382325_db48e7493dc23766455d60d9635fb3a2
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2013.05.014
dc.rightshttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectgraph coloring problem
dc.subjectgraph operators
dc.subjectmax-coloring problem
dc.subjectpolynomial-time algorithm
dc.titleA note on the Cornaz-Jost transformation to solve the graph coloring problem
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución