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:








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, Abstract, ©

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},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Evelyn Haak
Created
04/25/1997 04:36:59 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Uwe Brahm
Christos Zaroliagis
Christos Zaroliagis
Christos Zaroliagis
Edit Dates
01.04.99 17:15:19
30.03.99 22:41:39
25/02/99 18:37:42
25/02/99 18:34:59
03/30/98 06:40:31 PM