de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

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

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-112.pdf
(beliebiger Volltext), 125KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B50A-6
Zusammenfassung
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)$.