Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Chaudhuri, Shiva Zaroliagis, Christos dblp dblp
 BibTeX cite key*: Chaudhuri-Zaroliagis-2-97

 Title
 Title*: Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms

 Journal
 Journal Title*: Theoretical Computer Science Journal's URL: Download URL for the article: Language: English

 Publisher
 Publisher's Name: Publisher's URL: Publisher's Address: ISSN: 0304-3975

 Vol, No, pp, Date
 Volume*: 203 Number: 2 Publishing Date: 1998 Pages*: 205-223 Number of VG Pages: Page Start: Page End: Sequence Number: DOI:

 Note: Special issue on ESA'95 (LaTeX) Abstract: We consider the problem of preprocessing an $n$-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered. We give parallel algorithms for the EREW PRAM model of computation that depend on the {\em treewidth} of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in $O(\alpha(n))$ time using a single processor, after a preprocessing of $O(\log^2n)$ time and $O(n)$ work, where $\alpha(n)$ is the inverse of Ackermann's function. The class of constant treewidth graphs contains outerplanar graphs and series-parallel graphs, among others. To the best of our knowledge, these are the first parallel algorithms which achieve these bounds for any class of graphs except trees. We also give a dynamic algorithm which, after a change in an edge weight, updates our data structures in $O(\log n)$ time using $O(n^\beta)$ work, for any constant $0 < \beta < 1$. Moreover, we give an algorithm of independent interest: computing a shortest path tree, or finding a negative cycle in $O(\log^2 n)$ time using $O(n)$ work. URL for the Abstract: Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level:

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:

@ARTICLE{Chaudhuri-Zaroliagis-2-97,
AUTHOR = {Chaudhuri, Shiva and Zaroliagis, Christos},
TITLE = {Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms},
JOURNAL = {Theoretical Computer Science},
YEAR = {1998},
NUMBER = {2},
VOLUME = {203},
PAGES = {205--223},
ISBN = {0304-3975},
NOTE = {Special issue on ESA'95},
}