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 is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.

• Publication year

  2013

• Venue

  Computers & Operations Research

• Publication date

  2013-06-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.cor.2014.11.014arXiv 1306.1758
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computers And Intractability A Guide To The Theory Of Np Completeness

  2016cited by this paper
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives

  2014influential reference
• Graph Coloring Algorithms

  2014cited by this paper
• An exact DSatur-based algorithm for the Equitable Coloring Problem

  2014cited by this paper
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

  2013cited by this paper
• A new DSATUR-based algorithm for exact vertex coloring

  2012influential reference
• A polyhedral approach for the equitable coloring problem

  2011cited by this paper
• An Ore-type theorem on equitable coloring

  2008cited by this paper
• THE EQUITABLE COLORINGS OF KNESER GRAPHS

  2008cited by this paper
• A Branch-and-Cut algorithm for graph coloring

  2006cited by this paper
• Conflict-free star-access in parallel memory systems

  2006cited by this paper
• The Complexity of Equitable Vertex Coloring of Graphs

  2005cited by this paper
• On the asymmetric representatives formulation for the vertex coloring problem

  2005cited by this paper
• Equitable colorings extend Chernoff-Hoeffding bounds

  2001cited by this paper
• Equitable Coloring of Graphs

  1998cited by this paper
• Cliques, Coloring, and Satisfiability

  1996cited by this paper
• Equitable Coloring of Trees

  1994cited by this paper
• An improved algorithm for exact graph coloring

  1993cited by this paper
• New methods to color the vertices of a graph

  1979influential reference
• Compactness and balancing in scheduling

  1977cited by this paper
• Perfect Graphs and an Application to Optimizing Municipal Services

  1973cited by this paper
• Chromatic Scheduling and the Chromatic Number Problem

  1972cited by this paper
• GRAPH COLORING ALGORITHMS

  1972cited by this paper
• Proof of a conjecture of P. Erdös on the derivative of a polynomial

  1944cited by this paper

• Enhancement of LTE and NR systems through efficient physical cell identity allocation

  2026cites this paper
• A Graph-Theoretic Solution to NP-Complete Sudoku Puzzles: Malatya Centrality for Large-Scale Optimization

  2025cites this paper
• Optimality of DSatur algorithm on chordal graphs

  2024cites this paper
• Equitable coloring and scheduling on identical machines

  2022cites this paper
• Improving lower bounds for equitable chromatic number

  2022cites this paper
• Improving Lower Bounds for Equitable Chromatic Number

  2021cites this paper
• The Allocation and Reuse Scheme of Physical Cell Identifications Based on Maximum Degree First Coloring Algorithm

  2020cites this paper
• Memetic search for the equitable coloring problem

  2020cites this paper
• Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs

  2020cites this paper
• Population-based gradient descent weight learning for graph coloring problems

  2019cites this paper
• Gradient Descent based Weight Learning for Grouping Problems: Application on Graph Coloring and Equitable Graph Coloring

  2019cites this paper
• Tabu search with feasible and infeasible searches for equitable coloring

  2018influential citation
• An Improved DSATUR‐Based Branch‐and‐Bound Algorithm for the Vertex Coloring Problem

  2017cites this paper
• Solving Vertex Coloring Problems as Maximum Weighted Stable Set Problems

  2017cites this paper
• On feasible and infeasible search for equitable graph coloring

  2017influential citation
• Exact algorithms for the Vertex Coloring Problem and its generalisations. (Résolution exacte du Problème de Coloration de Graphe et ses variantes)

  2017cites this paper
• A flow based pruning scheme for enumerative equitable coloring algorithms

  2016influential citation
• Spectrum graph coloring and applications to WiFi channel assignment

  2016cites this paper
• Backtracking based iterated tabu search for equitable coloring

  2015influential citation
• An improved DSATUR-based Branch and Bound for the Vertex Coloring Problem

  2015cites this paper
• A Tabu Search Heuristic for the Equitable Coloring Problem

  2014cites this paper