License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2452
URN: urn:nbn:de:0030-drops-24523
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2452/
Chakraborty, Sourav ;
Fischer, Eldar ;
Lachish, Oded ;
Yuster, Raphael
Two-phase Algorithms for the Parametric Shortest Path Problem
Abstract
A {\em parametric weighted graph} is a graph whose edges are labeled with continuous real functions of a single common variable. For any instantiation of the variable, one obtains a standard edge-weighted graph. Parametric weighted graph problems are generalizations of weighted graph problems, and arise in various natural scenarios. Parametric weighted graph algorithms consist of two phases. A {\em preprocessing phase} whose input is a parametric weighted graph, and whose output is a data structure, the advice, that is later used by the {\em instantiation phase}, where a specific value for the variable is given. The instantiation phase outputs the solution to the (standard) weighted graph problem that arises from the instantiation. The goal is to have the running time of the instantiation phase supersede the running time of any algorithm that solves the weighted graph problem from scratch, by taking advantage of the advice.
In this paper we construct several parametric algorithms for the
shortest path problem. For the case of linear function weights we
present an algorithm for the single source shortest path problem. Its
preprocessing phase runs in $\tilde{O}(V^4)$ time, while its instantiation phase runs in only $O(E+V \log V)$ time. The fastest standard algorithm for single source shortest path runs in $O(VE)$ time. For the case of weight functions defined by degree $d$ polynomials, we present an algorithm with quasi-polynomial preprocessing time $O(V^{(1 + \log f(d))\log V})$ and instantiation time only $\tilde{O}(V)$. In fact, for any pair of vertices $u,v$, the instantiation phase computes the distance from $u$ to $v$ in only $O(\log^2 V)$ time. Finally, for linear function weights, we present
a randomized algorithm whose preprocessing time is $\tilde{O (V^{3.5})$ and so that for any pair of vertices $u,v$ and any instantiation variable, the instantiation phase computes, in $O(1)$ time, a length of a path from $u$ to $v$ that is at most (additively) $\epsilon$ larger than the length of a shortest path. In particular, an all-pairs shortest path solution, up to an additive constant error, can be computed in $O(V^2)$ time.
BibTeX - Entry
@InProceedings{chakraborty_et_al:LIPIcs:2010:2452,
author = {Sourav Chakraborty and Eldar Fischer and Oded Lachish and Raphael Yuster},
title = {{Two-phase Algorithms for the Parametric Shortest Path Problem}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {167--178},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-16-3},
ISSN = {1868-8969},
year = {2010},
volume = {5},
editor = {Jean-Yves Marion and Thomas Schwentick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2452},
URN = {urn:nbn:de:0030-drops-24523},
doi = {10.4230/LIPIcs.STACS.2010.2452},
annote = {Keywords: Parametric Algorithms, Shortest path problem}
}
|
Keywords: |
|
Parametric Algorithms, Shortest path problem |
|
Collection: |
|
27th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
09.03.2010 |
