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

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Giandomenico, M., Rossi, F.
Formato: JOUR
Materias:
Computational complexity
Graph coloring problem
Graph operators
Max-coloring problem
Polynomial-time algorithm
Coloring problems
Graph class
Max-coloring
Polynomial-time
Polynomial-time algorithms
Stable set problems
Algorithms
Polynomial approximation
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
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_ 1807322211718004736

Ejemplares similares