A DSATUR-based algorithm for the Equitable Coloring Problem

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

References in corpus (1)

• An exact DSatur-based algorithm for the Equitable Coloring Problem

Cited by in corpus (4)

• Spectrum graph coloring and applications to WiFi channel assignment
• Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
• Population-based Gradient Descent Weight Learning for Graph Coloring Problems
• A flow based pruning scheme for enumerative equitable coloring algorithms