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):

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

URL of the conference:

http://pauillac.inria.fr/~levy/TCS2004/

URL for downloading the paper:

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

View attachments here:


File Attachment Icon
emst.pdf