MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Crauser, Andreas
Mehlhorn, Kurt
Meyer, Ulrich		dblp
dblp
dblp
Editor(s):
Spaniol, Ottodblp
BibTeX cite key*:
CraMehMey97
Title, Booktitle
Title*:
Kürzeste-Wege-Berechnung bei sehr großen Datenmengen
Booktitle*:
Promotion tut not: Innovationsmotor "Graduiertenkolleg"
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Aachen, Germany
Language:
German
Event Date*
(no longer used):
September, 22-23
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Augustinus
URL:
Address*:
Aachen, Germany
Type:
Vol, No, Year, pp.
Series:
Aachener Beiträge zur Informatik
Volume:
21
Number:
Month:
September
Pages:
113-132
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
3-86073-477-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In diesem Report untersuchen wir die Ein/Ausgabe-Komplexität (I/O Komplexität) des Kürzesten-Wege-Problems mit einem Startknoten (single source shortest path) auf Graphen mit nicht-negativen Kantengewichten. Wir präsentieren einen Algorithmus, der für eine große Klasse zufälliger Graphen eine I/O Komplexität von ${\cal O}(\frac{n}{D}+\frac{m}{DB}\log_{S/B}\frac{m}{B})$ erreicht. Dabei bezeichnen $n,m$ die Anzahl der Knoten bzw. Kanten im Graphen, $S$ ist die Größe des verfügbaren Internspeichers, $B$ bezeichnet die Größe eines Blocktransfers und $D$ ist die Anzahl der unabhängigen
parallelen Harddisks; $D$ ist beschränkt auf ${\cal O}(\sqrt{n/d})$.
Weiterhin präsentieren wir ein effizientes Phasen-Verfahren für Probleminstanzen, die so groß sind, daß selbst ein boolsches Feld für die Knotenmenge nicht mehr im Hauptspeicher gehalten werden kann.
Keywords:
I/O Komplexität, Kürzeste-Wege-Berechnung, Externspeicher, zufällige Graphen
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{CraMehMey97,
AUTHOR = {Crauser, Andreas and Mehlhorn, Kurt and Meyer, Ulrich},
 EDITOR = {Spaniol, Otto},
 TITLE = {K{\"u}rzeste-Wege-Berechnung bei sehr großen Datenmengen},
 BOOKTITLE = {Promotion tut not: Innovationsmotor "Graduiertenkolleg"},
 PUBLISHER = {Augustinus},
 YEAR = {1997},
 VOLUME = {21},
 PAGES = {113--132},
 SERIES = {Aachener Beiträge zur Informatik},
 ADDRESS = {Aachen, Germany},
 MONTH = {September},
 ISBN = {3-86073-477-6},
}

Entry last modified by Uwe Brahm, 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)
Ulrich Meyer		Created
09/24/1997 06:55:25 PM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
03/11/2008 06:39:49 PM
03/11/2008 02:48:32 PM
29.03.2006 14:22:54
29.03.2006 14:20:26
30/03/98 14:22:34