Manuel Castaneda-FalconMinimale spannende Aborescencen mit Zeitfenstern

Zum Inhalt

In dieser Arbeit werden Verfahren vorgestellt, um Schranken für die Gesamtsumme der Kantenbewertungen eines MSAZF (minimaler spannender Arborescence mit Zeitfenstern) zu bestimmen: Ein heuristisches Verfahren und Verfahren zur Bestimmung von unteren Schranken.

Zuerst werden die für diese Arbeit notwendigen Grunddefinitionen bei endlichen Graphen angegeben. Anschließend werden einige bekannte Lösungsverfahren für das MST-Problem sowie für das MSA-Problem erläutert und ihre Arbeitsweise anhand von Beispielen veranschaulicht.

Ausgehend von dem Beispiel der Übertragung einer Botschaft in einem Straßennetz werden die Begriffe eingeführt, die für die Entwicklung der Verfahren notwendig sind. Danach wird ein heuristisches Verfahren zur Bestimmung eines spannenden Arborescences mit Zeitfenstern vorgestellt. Es werden zwei LP-Formulierungen für das MSAZF-Problem sowie die bekannten Ansätze und Werkzeuge aus der Theorie der linearen Programmierung vorgestellt, die ausgehend von diesen LP-Formulierungen für die Gewinnung von unteren Schranken in Frage kommen. Dann werden die Verfahren zur Bestimmung der unteren Schranken vorgestellt und diese Verfahren schließlich auf konkrete numerische Beispiele angewendet.