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 02:57:08 PM
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