Graphenfärbung mit Hilfe linearer Programmierung


Diplomarbeit, 2005

156 Seiten, Note: 1.0

Alessandro Tomazic (Autor)


Inhaltsangabe oder Einleitung

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.

Details

Titel
Graphenfärbung mit Hilfe linearer Programmierung
Hochschule
Universität Augsburg  (Institut für Mathematik)
Note
1.0
Autor
Jahr
2005
Seiten
156
Katalognummer
V996591
Sprache
Deutsch
Schlagworte
Graph coloring, operations research, combinatorial optimization, branch and price, integer programming
Arbeit zitieren
Alessandro Tomazic (Autor), 2005, Graphenfärbung mit Hilfe linearer Programmierung, München, GRIN Verlag, https://www.grin.com/document/996591

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Graphenfärbung mit Hilfe linearer Programmierung



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden