English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On-line and dynamic algorithms for shortest path problems

MPS-Authors
/persons/resource/persons44333

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

/persons/resource/persons45787

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-94-114.pdf
(Any fulltext), 129KB

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

Djidjev, H., Pantziou, G. E., & Zaroliagis, C.(1994). On-line and dynamic algorithms for shortest path problems (MPI-I-94-114). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B514-E
Abstract
We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in 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. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our results can be extended to hold for digraphs of genus $o(n)$.