de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On-line and Dynamic Shortest Paths through Graph Decompositions (Preliminary Version)

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44333

Djidjev,  Hristo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-94-112.pdf
(Any fulltext), 125KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Djidjev, H., Pantziou, G. E., & Zaroliagis, C.(1994). On-line and Dynamic Shortest Paths through Graph Decompositions (Preliminary Version) (MPI-I-94-112). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B50A-6
Abstract
We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. We give both sequential and parallel algorithms that work on a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. The parallel algorithms presented here are the first known ones for solving this problem. Our results can be extended to hold for digraphs of genus $o(n)$.