A DSATUR-based algorithm for the equitable coloring problem

DOI10.1016/J.COR.2014.11.014MaRDI QIDQ337479zbMATH OpenOpenAlexFDO

Authors Isabel Méndez-Díaz, D. Severín, G. Nasini

Publication date 10 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.1758, http://hdl.handle.net/11336/38356

zbMATH Keywords

exact algorithmequitable coloring\textsc{DSsatur}

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• A tabu search heuristic for the equitable coloring problem
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
• A fast algorithm for equitable coloring
• Improving lower bounds for equitable chromatic number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• A branch-and-cut algorithm for graph coloring
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• A polyhedral approach for the equitable coloring problem
• An Ore-type theorem on equitable coloring
• Chromatic Scheduling and the Chromatic Number Problem
• Compactness and balancing in scheduling
• Conflict-free star-access in parallel memory systems
• Equitable Coloring
• Equitable coloring of trees
• New methods to color the vertices of a graph
• On the asymmetric representatives formulation for the vertex coloring problem
• Perfect Graphs and an Application to Optimizing Municipal Services
• The equitable colorings of Kneser graphs

Cited in

(8)

• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A flow based pruning scheme for enumerative equitable coloring algorithms
• Spectrum graph coloring and applications to Wi-Fi channel assignment
• A fast algorithm for equitable coloring
• Polyhedral results for the equitable coloring problem
• A polyhedral approach for the equitable coloring problem
• A tabu search heuristic for the equitable coloring problem
• Improving lower bounds for equitable chromatic number

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A DSATUR-based algorithm for the equitable coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q337479)