Artículo

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

Bonomo, FlaviaIcon ; Giandomenico, Monia; Rossi, Fabrizio
Fecha de publicación: 04/06/2013
Editorial: Elsevier Science Bv
Revista: Information Processing Letters
ISSN: 0020-0190
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

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.
Palabras clave: Graph Coloring Problem , Graph Operators , Max-Coloring Problem , Polynomial-Time Algorithm
 
Archivos asociados
Thumbnail
 
Tamaño: 186.9Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/733
URL: http://www.sciencedirect.com/science/article/pii/S0020019013001567#
DOI: http://dx.doi.org/10.1016/j.ipl.2013.05.014
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Citación
Bonomo, 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
Compartir
Altmétricas