A note on the Cornaz-Jost transformation to solve the graph coloring problem
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. © 2013 Elsevi...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | JOUR |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo |
Aporte de: |
id |
todo:paper_00200190_v113_n18_p649_Bonomo |
---|---|
record_format |
dspace |
spelling |
todo:paper_00200190_v113_n18_p649_Bonomo2023-10-03T14:16:39Z A note on the Cornaz-Jost transformation to solve the graph coloring problem Bonomo, F. Giandomenico, M. Rossi, F. Computational complexity Graph coloring problem Graph operators Max-coloring problem Polynomial-time algorithm Coloring problems Graph class Graph coloring problem Max-coloring Polynomial-time Polynomial-time algorithms Stable set problems Algorithms Computational complexity Polynomial approximation Graph theory 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. © 2013 Elsevier B.V. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Computational complexity Graph coloring problem Graph operators Max-coloring problem Polynomial-time algorithm Coloring problems Graph class Graph coloring problem Max-coloring Polynomial-time Polynomial-time algorithms Stable set problems Algorithms Computational complexity Polynomial approximation Graph theory |
spellingShingle |
Computational complexity Graph coloring problem Graph operators Max-coloring problem Polynomial-time algorithm Coloring problems Graph class Graph coloring problem Max-coloring Polynomial-time Polynomial-time algorithms Stable set problems Algorithms Computational complexity Polynomial approximation Graph theory Bonomo, F. Giandomenico, M. Rossi, F. A note on the Cornaz-Jost transformation to solve the graph coloring problem |
topic_facet |
Computational complexity Graph coloring problem Graph operators Max-coloring problem Polynomial-time algorithm Coloring problems Graph class Graph coloring problem Max-coloring Polynomial-time Polynomial-time algorithms Stable set problems Algorithms Computational complexity Polynomial approximation Graph theory |
description |
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. © 2013 Elsevier B.V. |
format |
JOUR |
author |
Bonomo, F. Giandomenico, M. Rossi, F. |
author_facet |
Bonomo, F. Giandomenico, M. Rossi, F. |
author_sort |
Bonomo, F. |
title |
A note on the Cornaz-Jost transformation to solve the graph coloring problem |
title_short |
A note on the Cornaz-Jost transformation to solve the graph coloring problem |
title_full |
A note on the Cornaz-Jost transformation to solve the graph coloring problem |
title_fullStr |
A note on the Cornaz-Jost transformation to solve the graph coloring problem |
title_full_unstemmed |
A note on the Cornaz-Jost transformation to solve the graph coloring problem |
title_sort |
note on the cornaz-jost transformation to solve the graph coloring problem |
url |
http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo |
work_keys_str_mv |
AT bonomof anoteonthecornazjosttransformationtosolvethegraphcoloringproblem AT giandomenicom anoteonthecornazjosttransformationtosolvethegraphcoloringproblem AT rossif anoteonthecornazjosttransformationtosolvethegraphcoloringproblem AT bonomof noteonthecornazjosttransformationtosolvethegraphcoloringproblem AT giandomenicom noteonthecornazjosttransformationtosolvethegraphcoloringproblem AT rossif noteonthecornazjosttransformationtosolvethegraphcoloringproblem |
_version_ |
1782029112450220032 |