Projekt: Branch- and Bound Algorithmen für das equitable Graphenfärbungsproblem

Förderung: DFG Exellence Initiative
Lehrstuhl II für Mathematik, Lehr- und Forschungsgebiet Diskrete Optimierung
RWTH Aachen University

Overview / The equitable coloring problem / Code and Data /


The project approaches the the equitable graph coloring problem. An equitable graph coloring is a vertex coloring, such that the size of the color classes differ by at most one. In applications, this problem arises, for example, in scheduling problems where tasks should be assigned to workers or machines in a fair manner.
Fig.1 - An equitable coloring of a graph

In this project, we consider a flow-based scheme for generating pruning rules for enumerative algorithms such as DSATUR. Such scheme models the extendability of a partial (equitable) coloring into an equitable coloring via network flows. We extend on the undergraduate funds project Implementation of a new branch and bound algorithm for the equitable coloring problem (IBBVeF) by Sven Förster. The aim of this project is to find further theoretical results and to develop a state of the art C++ implementation of such branch and bound algorithm.


Project head: Prof. Arie M.C.A. Koster
Dr. Robert B. Scheidweiler
Martin Tieves
Student assistants: Duc Thanh Tran and Sven Förster (former)


An introduction: A DSATUR-based algorithm for the Equitable Coloring Problem, Méndez-Díaz, Nasini und Severín (link).
Preprint (Arxiv): A flow based pruning scheme for enumerative equitable coloring algorithms, Koster, Scheidweiler and Tieves (link).

Conferences and Presentations

A flow based pruining scheme for enumerative equitable coloring algorithms, Martin Tieves, INFORMS Optimization Society Conference 2016, Princeton, NY, US (link).

Pruining Schemes for DSATUR algorithms for equitable graph coloring, Robert B. Scheidweiler, Oberseminar, Zuse Institute, Berlin, Germany.

Generating Pruning Rules For Enumerative Equitable Coloring Algorithms, International Symposium on Combinatorial Optimisation 2016, University of Kent, Canterbury, UK.
last modified: 13/02/2017 - 17:21