INVESTIGADORES
BONOMO flavia
artículos
Título:
A note on the Cornaz-Jost transformation to solve the graph coloring problem
Autor/es:
BONOMO, FLAVIA; GIANDOMENICO, MONIA; ROSSI, FABRIZIO
Revista:
INFORMATION PROCESSING LETTERS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2013 vol. 113 p. 649 - 652
ISSN:
0020-0190
Resumen:
In 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.
