Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Crauser, Andreas
Mehlhorn, Kurt
Meyer, Ulrich

dblp
dblp
dblp



Editor(s):

Spaniol, Otto

dblp



BibTeX cite key*:

CraMehMey97

Title, Booktitle

Title*:

Kürzeste-Wege-Berechnung bei sehr großen Datenmengen

Booktitle*:

Promotion tut not: Innovationsmotor "Graduiertenkolleg"

Event, URLs

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:




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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section