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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.167-178, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455816
Contributor : Publications Loria <>
Submitted on : Thursday, February 11, 2010 - 12:03:11 PM
Last modification on : Thursday, February 11, 2010 - 12:57:17 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 8:14:11 PM

File

chakraborty.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455816, version 1

Collections

Citation

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Raphael Yuster. Two-phase algorithms for the parametric shortest path problem. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.167-178, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455816>

Share

Metrics

Record views

154

Document downloads

313