Please use this identifier to cite or link to this item: doi:10.22028/D291-25863
Title: Average-case complexity of shortest-paths problems
Author(s): Priebe, Volker
Language: English
Year of Publication: 2001
SWD key words: Kürzester-Weg-Problem
Average-case-Komplexität
Free key words: average-case complexity
shortest-paths algorithm
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: We study both upper and lower bounds on the average-case complexity of shortestpaths algorithms. It is proved that the all-pairs shortest-paths problem on n-vertex networks can be solved in time O(n^2 log n) with high probability with respect to various probability distributions on the set of inputs. Our results include the first theoretical analysis of the average behavior of shortest-paths algorithms with respect to the vertex-potential model, a family of probability distributions on complete networks with arbitrary real arc costs but without negative cycles. We also generalize earlier work with respect to the common uniform model, and we correct the analysis of an algorithm with respect to the endpoint-independent model. For the algorithm that solves the all-pairs shortest-paths problem on networks generated according to the vertex-potential model, a key ingredient is an algorithm that solves the single-source shortest-paths problem on such networks in time O(n^2) with high probability. All algorithms mentioned exploit that with high probability, the single-source shortest-paths problem can be solved correctly by considering only a rather sparse subset of the arc set. We prove a lower bound indicating the limitations of this approach. In a fairly general probabilistic model, any algorithm solving the single-source shortest-paths problem has to inspect OMEGA(n log n) arcs with high probability.
In dieser Arbeit werden sowohl obere als auch untere Schranken für die average-case-Komplexität von Kürzeste-Wege-Algorithmen untersucht. Wir beweisen für verschiedene Wahrscheinlichkeitsverteilungen auf Netzwerken mit n Knoten, dass das all-pairs shortest-paths problem mit hoher Wahrscheinlichkeit in Zeit O(n^2 log n) gelöst werden kann. Insbesondere können wir dieses Laufzeit für einen Algorithmus beweisen, dessen Eingaben gemäß des vertex-potential model erzeugt werden, einer Familie von Wahrscheinlichkeitsverteilungen auf vollständigen Netzwerke mit reellen Kantenkosten, die jedoch keine negative Kreise besitzen. Theoretische Ergebnisse für dieses Eingabemodell waren bislang nicht bekannt. Wir verallgemeinern außerdem frühere Arbeit bezüglich des uniform model und korrigieren die Laufzeit-Analyse eines Algorithmus bezüglich des endpoint-independent model. Der Algorithmus, der das all-pairs shortest-paths problem auf Netzwerken löst, die gemäß des vertex-potential model erzeugt werden, baut entscheidend darauf auf, dass wir auch einen Algorithmus entwickeln, der das single-source shortest-paths problem auf solchen Netzwerken mit hoher Wahrscheinlichkeit in Zeit O(n^2) löst. Alle bislang erwähnten Algorithmen nutzen aus, dass das single-source shortest-paths problem auch dann mit hoher Wahrscheinlichkeit korrekt gelöst werden kann, wenn wir nur einen Teil der Kantenmenge betrachten. Wir beweisen eine untere Schranke, die die Grenzen dieses Reduktionsansatzes belegt. Auf einer Klasse von Netzwerken mit ganzzahligen Kantenkosten muss jeder Algorithmus mit hoher Wahrscheinlichkeit OMEGA(n log n) Kanten inspizieren, um das single-source shortest-paths problem zu lösen.
Link to this record: urn:nbn:de:bsz:291-scidok-11807
hdl:20.500.11880/25919
http://dx.doi.org/10.22028/D291-25863
Advisor: Mehlhorn, Kurt
Date of oral examination: 1-Jun-2001
Date of registration: 6-Jul-2007
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_5735_Prie_Volk_2001.pdf459,63 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.