MPI-INF D1 Publications: Proceedings Article: Kürzeste-Wege-Berechnung bei sehr großen Datenmengen

URL of the conference:
URL for downloading the paper:
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:


(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

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

Attachment Section