MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Dementiev, Roman
Sanders, Peter
Schultes, Dominik
Sibeyn, Jop F.		dblp
dblp
dblp
dblp
Not MPG Author(s):
Sibeyn, Jop F.
Editor(s):
Lévy,Jean-Jacques
Mayr, Ernst W.
Mitchell, John C.		dblp
dblp
dblp
Not MPII Editor(s):
Lévy,Jean-Jacques
Mayr, Ernst W.
Mitchell, John C.
BibTeX cite key*:
DSSS04
Title, Booktitle
Title*:
Engineering an External Memory Minimum Spanning Tree Algorithm
emst.pdf (185.48 KB)
Booktitle*:
3rd IFIP International Conference on Theoretical Computer Science (TSC2004)
Event, URLs
Conference URL::
http://pauillac.inria.fr/~levy/TCS2004/
Downloading URL:
http://i10www.ira.uka.de/dementiev/files/emst.ps
Event Address*:
Toulouse, France
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
23 August 2004
Event End Date:
26 August 2004
Publisher
Name*:
Kluwer
URL:
http://www.kluweronline.com/
Address*:
Norwell, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
195-208
Year*:
2004
VG Wort Pages:
14
ISBN/ISSN:
1-4020-8140-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We develop an external memory algorithm for computing minimum spanning
trees. The algorithm is considerably simpler than previously known
external memory algorithms for this problem and needs a factor of at
least four less I/Os for realistic inputs.

Our implementation indicates that this algorithm processes graphs only
limited by the disk capacity of most current machines in time no more
than a factor 2--5 of a good internal algorithm with sufficient memory
space.
Keywords:
secondary memory, random permutation, time forward processing, external priority queue, external graph algorithm
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{DSSS04,
AUTHOR = {Dementiev, Roman and Sanders, Peter and Schultes, Dominik and Sibeyn, Jop F.},
 EDITOR = {L{\'e}vy,Jean-Jacques and Mayr, Ernst W. and Mitchell, John C.},
 TITLE = {Engineering an External Memory Minimum Spanning Tree Algorithm},
 BOOKTITLE = {3rd IFIP International Conference on Theoretical Computer Science (TSC2004)},
 PUBLISHER = {Kluwer},
 YEAR = {2004},
 PAGES = {195--208},
 ADDRESS = {Toulouse, France},
 ISBN = {1-4020-8140-5},
}

Entry last modified by Christine Kiesel, 09/20/2006
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)
Roman Dementiev		Created
02/15/2005 14:57:08
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
20.09.2006 15:14:42
30.05.2005 16:49:43
30.05.2005 16:49:13
30.05.2005 15:29:01
11.04.2005 16:00:00

File Attachment Icon
emst.pdf