print page

Bachelor's Thesis

Bestimmung von Dominanzzahlen von Graphen mittels Linearer Programmierung

Kontext

Dominierende Mengen in Graphen werden seit vielen Jahren untersucht. Eine dominierende Menge eines Graphen ist folgendendermaßen definiert: Alle Knoten des Graphen können in höchstens einem Schritt von einem Knoten der dominierenden Menge erreicht werden. In der Regel ist man an der kleinsten dominierenden Menge interessiert. Die Bestimmung der Größe einer solchen Menge gehört zu der Klasse der NP-Vollständigen Probleme. Somit besteht so gut wie keine Hoffnung, ein effizientes Verfahren für die Bestimmung der Dominanzzahl zu finden. Die Kenntnis dominierender Mengen hat viele praktische Anwendungen, beispielsweise bei der Standortbestimmung von Sendemasten in Funknetzen.

Es gibt zahlreiche Varianten der Definition einer dominierenden Menge. Beispielsweise die totale Dominanz, dabei wird zusätzlich gefordert, dass jeder Knoten einer dominierenden Menge in einem Schritt von einem anderen Knoten der dominierenden Menge erreichbar ist.

Für einige spezielle Klassen von Graphen kennt man die Anzahl der Knoten einer minimalen dominierenden Menge. Das Problem der minimal dominierenden Menge kann als Integer-LP Problem formuliert werden. Leider lassen sich solche Probleme ebenfalls nicht effizient lösen. Häufig bekommt man aber auf diese Art zumindest eine untere Abschätzung.

Aufgabe

In dieser Bachelorarbeit sollen für verschiedene Klassen von Graphen und verschiedene Dominanzprobleme lineareProgrammeerstelltundgelöstwerden. Für diese Graphen sollen dieminimalen Dominanzzahlen bestimmt werden. Kandidaten für diese Bachelorarbeit sollten Kenntnisse in diskreter Mathematik und Programmierung haben. Als LP-Löser stehen verschiedene Werzeuge zur Verfügung, beispielsweise MATLAB, Octave, Gurobi.

Documents Flyer
Contact Prof. Dr. rer. nat. Volker Turau