KIT | KIT-Bibliothek | Impressum | Datenschutz

Shortest-Path Indices: Establishing a Methodology for Shortest-Path Problems

Bauer, Reinhard; Delling, Daniel; Wagner, Dorothea

Abstract:

During the last years, impressive progress has been achieved in
the field of algorithm engineering. A problem becoming more and
more important is that of data dependency: the performance of an
algorithm often highly depends on the input. Yet, for a given
input, it is highly non-trivial to select the best solving strategy.

In this work, we introduce a new methodology for evaluating
speed-up techniques for DijkstraŽs Algorithm: we examine the
shortest-path structure of networks using simple indices in
order to predict how well speed-up techniques perform on
specific networks. More precisely, we introduce the ReCo-Index
that indicates the strength of hierarchy of the input. In
addition, we present a second index, called shortest-path
entropy, taking into account the mutual importance of
consecutive edges. As a third index, the update impact measures
the change of the shortest-paths structure in a network whenever
it is altered. For each index, we present an algorithm for
computing it efficiently. An experimental evaluation confirms
the correlation of indices and speed-up techniques.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000006961
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2007
Sprache Englisch
Identifikator ISSN: 1432-7864
urn:nbn:de:swb:90-69619
KITopen-ID: 1000006961
Verlag Universität Karlsruhe, Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2007,14
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page