Graphenfärbung mit Hilfe linearer Programmierung

Diese Arbeit behandelt ein Verfahren zur Lösung eines schwierigen Problems aus der kombinatorischen Optimierung, der Graphenfärbung.

Dieses in [MT] beschriebene Verfahren bedient sich linearer Programmierung und eines klassischen diskreten Optimierungsproblems. Für dieses "Unabhängige Mengen"-Problem wird hier ein bewährtes Verfahren besprochen und zusätzlich ein recht effizientes Verfahren eingeführt. Durch Einführungen in alle behandelten Optimierungsprobleme anhand von Beispielen und klaren Definitionen soll sich auch der noch nicht auf das Gebiet der kombinatorischen Optimierung vorgedrungene Leser zurechtfinden können.

Da Algorithmen und Ideen für ihre Umsetzung die Zentrale Rolle spielen, sind die wichtigsten Verfahren in einfach zu verstehendem Pseudocode angegeben und Details anschließend erläutert. Ein eigenes Kapitel behandelt die Implementierung (etwa 6300 Zeilen reiner Code) und erklärt praktische Einzelheiten. Die in Tabellen aufgelisteten Testergebnisse für verschiedene Problemintanztypen geben Informationen für Vergleiche mit anderen Verfahren oder Implementierungen.