English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  On-line and Dynamic Shortest Paths through Graph Decompositions (Preliminary Version)

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.

Item is

Files

show Files
hide Files
:
MPI-I-94-112.pdf (Any fulltext), 125KB
Name:
MPI-I-94-112.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Djidjev, Hristo1, Author           
Pantziou, Grammati E.2, Author
Zaroliagis, Christos1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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)$.

Details

show
hide
Language(s): eng - English
 Dates: 1994
 Publication Status: Issued
 Pages: 14 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/94-112
Report Nr.: MPI-I-94-112
BibTex Citekey: DjidjevPantziouZaroliagis94a
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -