A DSATUR-based algorithm for the Equitable Coloring Problem

This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Méndez-Díaz, I., Nasini, G., Severín, D.
Formato: JOUR
Materias:
DSatur
Equitable coloring
Exact algorithm
Benchmarking
Coloring
Arbitrary color
Coloring problems
Computational experiment
Exact algorithms
Algorithms
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03050548_v57_n_p41_MendezDiaz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03050548_v57_n_p41_MendezDiaz
record_format dspace
spelling todo:paper_03050548_v57_n_p41_MendezDiaz2023-10-03T15:21:24Z A DSATUR-based algorithm for the Equitable Coloring Problem Méndez-Díaz, I. Nasini, G. Severín, D. DSatur Equitable coloring Exact algorithm Benchmarking Coloring Arbitrary color Coloring problems Computational experiment DSatur Equitable coloring Exact algorithms Algorithms This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances. © 2014 Elsevier Ltd. All rights reserved. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Severín, D. 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_03050548_v57_n_p41_MendezDiaz
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic DSatur
Equitable coloring
Exact algorithm
Benchmarking
Coloring
Arbitrary color
Coloring problems
Computational experiment
DSatur
Equitable coloring
Exact algorithms
Algorithms
spellingShingle DSatur
Equitable coloring
Exact algorithm
Benchmarking
Coloring
Arbitrary color
Coloring problems
Computational experiment
DSatur
Equitable coloring
Exact algorithms
Algorithms
Méndez-Díaz, I.
Nasini, G.
Severín, D.
A DSATUR-based algorithm for the Equitable Coloring Problem
topic_facet DSatur
Equitable coloring
Exact algorithm
Benchmarking
Coloring
Arbitrary color
Coloring problems
Computational experiment
DSatur
Equitable coloring
Exact algorithms
Algorithms
description This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances. © 2014 Elsevier Ltd. All rights reserved.
format JOUR
author Méndez-Díaz, I.
Nasini, G.
Severín, D.
author_facet Méndez-Díaz, I.
Nasini, G.
Severín, D.
author_sort Méndez-Díaz, I.
title A DSATUR-based algorithm for the Equitable Coloring Problem
title_short A DSATUR-based algorithm for the Equitable Coloring Problem
title_full A DSATUR-based algorithm for the Equitable Coloring Problem
title_fullStr A DSATUR-based algorithm for the Equitable Coloring Problem
title_full_unstemmed A DSATUR-based algorithm for the Equitable Coloring Problem
title_sort dsatur-based algorithm for the equitable coloring problem
url http://hdl.handle.net/20.500.12110/paper_03050548_v57_n_p41_MendezDiaz
work_keys_str_mv AT mendezdiazi adsaturbasedalgorithmfortheequitablecoloringproblem
AT nasinig adsaturbasedalgorithmfortheequitablecoloringproblem
AT severind adsaturbasedalgorithmfortheequitablecoloringproblem
AT mendezdiazi dsaturbasedalgorithmfortheequitablecoloringproblem
AT nasinig dsaturbasedalgorithmfortheequitablecoloringproblem
AT severind dsaturbasedalgorithmfortheequitablecoloringproblem
_version_ 1782023494930792448

Ejemplares similares