Projekt: Branch- and Bound Algorithmen für das equitable Graphenfärbungsproblem
Overview / The equitable coloring problem / Code and Data /
Description
-
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.
Staff
Project head: Prof. Arie M.C.A. Koster
Publications
An introduction: A DSATUR-based algorithm for the Equitable Coloring Problem, Méndez-Díaz, Nasini und Severín (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).
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.
Dr. Robert B. Scheidweiler
Martin Tieves
Student assistants: Duc Thanh Tran and Sven Förster (former)
Preprint (Arxiv): A flow based pruning scheme for enumerative equitable coloring algorithms, Koster, Scheidweiler and Tieves (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
math2.rwth-aachen.de