A DSATUR-based algorithm for the equitable coloring problem

DOI10.1016/J.COR.2014.11.014zbMATH Open1348.05205arXiv1306.1758OpenAlexW2102068573MaRDI QIDQ337479FDOQ337479

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)

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.

Full work available at URL: https://arxiv.org/abs/1306.1758

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

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)

Cites Work

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

Cited In (8)

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

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)