Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475441 | Computers & Operations Research | 2015 | 10 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Isabel Méndez-Díaz, Graciela Nasini, Daniel Severín,