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

Bonomo, F.; Giandomenico, M.; Rossi, F

doi:http://dx.doi.org/10.1016/j.ipl.2013.05.014

CINECA IRIS Institutional Research Information System

IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/8419

Titolo:	A note on the Cornaz-Jost transformation to solve the graph coloring problem
Autori interni:	ROSSI, FABRIZIO
Data di pubblicazione:	2013
Rivista:	INFORMATION PROCESSING LETTERS
Abstract:	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.
Handle:	http://hdl.handle.net/11697/8419
Appare nelle tipologie:	1.1 Articolo in rivista

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Citazioni
ND

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.