MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Brodal, Gerth Stølting
Träff, Jesper Larsson
Zaroliagis, Christos		dblp
dblp
dblp
Editor(s):
Feitelson, Dror G.
Rudolph, Larry		dblp
dblp
BibTeX cite key*:
Brodal-Traeff-Zaro97
Title, Booktitle
Title*:
A parallel priority data structure with applications
Booktitle*:
11th Internatinal Parallel Processing Symposium (IPPS-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Geneva, Switzerland
Language:
English
Event Date*
(no longer used):
-
Organization:
Event Start Date:
1 April 1997
Event End Date:
5 April 1997
Publisher
Name*:
IEEE
URL:
Address*:
Los Alamitos, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
689-693
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present a parallel priority data structure that improves
the running time of certain algorithms for problems
that lack a fast and work-efficient parallel solution.
As a main application, we give a parallel implementation
of Dijkstra's algorithm which runs in $O(n)$ time
while performing $O(m\log n)$ work on a CREW PRAM\@.
This is a logarithmic factor improvement for the running
time compared with previous approaches. The main
feature of our data structure is that the operations needed
in each iteration of Dijkstra's algorithm can be
supported in $O(1)$ time.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Brodal-Traeff-Zaro97,
AUTHOR = {Brodal, Gerth Stølting and Tr{\"a}ff, Jesper Larsson and Zaroliagis, Christos},
 EDITOR = {Feitelson, Dror G. and Rudolph, Larry},
 TITLE = {A parallel priority data structure with applications},
 BOOKTITLE = {11th Internatinal Parallel Processing Symposium (IPPS-97)},
 PUBLISHER = {IEEE},
 YEAR = {1997},
 PAGES = {689--693},
 ADDRESS = {Geneva, Switzerland},
}

Entry last modified by Christine Kiesel, 03/02/2010
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 05:33:29 PM
Revisions
10.
9.
8.
7.
6.		Editor(s)
Christine Kiesel
Gerth Stølting Brodal
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
30.05.2005 16:38:41
23/01/99 20:17:22
04/02/98 04:45:14 PM
04/02/98 04:39:23 PM
04/02/98 04:18:26 PM