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:
Autor principal: | |
---|---|
Publicado: |
2013
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo |
Aporte de: |
id |
paper:paper_00200190_v113_n18_p649_Bonomo |
---|---|
record_format |
dspace |
spelling |
paper:paper_00200190_v113_n18_p649_Bonomo2023-06-08T14:40:21Z A note on the Cornaz-Jost transformation to solve the graph coloring problem Bonomo, Flavia 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. 2013 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo 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, Flavia 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. |
author |
Bonomo, Flavia |
author_facet |
Bonomo, Flavia |
author_sort |
Bonomo, Flavia |
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 |
publishDate |
2013 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo |
work_keys_str_mv |
AT bonomoflavia anoteonthecornazjosttransformationtosolvethegraphcoloringproblem AT bonomoflavia noteonthecornazjosttransformationtosolvethegraphcoloringproblem |
_version_ |
1768544350598332416 |