Reliable and Restricted Quickest Path Problems

  • In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Stefan Ruzika, Markus Thiemann
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16851
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (135)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2011
Jahr der Veröffentlichung:2011
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):02.03.2011
Freies Schlagwort / Tag:Dynamic Network Flows ; FPTAS ; Pseudopolynomial-Time Algorithm; Restricted Shortest Path
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $