: Minimale spannende Aborescencen mit Zeitfenstern

Minimale spannende Aborescencen mit Zeitfenstern

Heuristische Verfahren und untere Schranken

Schriftenreihe naturwissenschaftliche Forschungsergebnisse, Band 35

Hamburg , 130 Seiten

ISBN 978-3-86064-420-1 (Print)

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.

Ihr Werk im Verlag Dr. Kovač

Bibliothek, Bücher, Monitore

Möchten Sie Ihre wissenschaftliche Arbeit publizieren? Erfahren Sie mehr über unsere günstigen Konditionen und unseren Service für Autorinnen und Autoren.

Nach oben ▲