MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sibeyn, Jop F.
Abello, James
Meyer, Ulrich		dblp
dblp
dblp
Not MPG Author(s):
Sibeyn, Jop F.
Abello, James
Editor(s):
BibTeX cite key*:
SiAbMe02
Title, Booktitle
Title*:
Heuristics for Semi-External Depth First Search on Directed Graphs
Booktitle*:
SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Winnipeg, Canada
Language:
English
Event Date*
(no longer used):
-- August, 10 - August, 13
Organization:
ACM
Event Start Date:
10 August 2002
Event End Date:
13 August 2002
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
August
Pages:
282-292
Year*:
2002
VG Wort Pages:
35
ISBN/ISSN:
1-58113-529-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 Computing the strong components of a directed graph is an essential
operation for a basic structural analysis of it. This problem can
be solved by twice running a depth-first search (DFS).
In an external setting, in which all data can no longer be stored in
the main memory, the DFS problem is unsolved so far. Assuming that
node-related data can be stored internally, semi-external computing
does not make the problem substantially easier. Considering the
definite need to analyze very large graphs, we have developed a set
of heuristics which together allow the performance of semi-external DFS for
directed graphs in practice. The heuristics have been applied to
graphs with very different graph properties, including ``web graphs''
as described in the most recent literature and some call graphs from
ATT. Depending on the graph structure, the program is between 10 and
200 times faster than the best alternative, a factor that will
further increase with future technological developments.
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, VG Wort



BibTeX Entry:

@INPROCEEDINGS{SiAbMe02,
AUTHOR = {Sibeyn, Jop F. and Abello, James and Meyer, Ulrich},
 TITLE = {Heuristics for Semi-External Depth First Search on Directed Graphs},
 BOOKTITLE = {SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures},
 PUBLISHER = {ACM},
 YEAR = {2002},
 ORGANIZATION = {ACM},
 PAGES = {282--292},
 ADDRESS = {Winnipeg, Canada},
 MONTH = {August},
 ISBN = {1-58113-529-7},
}

Entry last modified by Christine Kiesel, 03/02/2010
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
08/19/2002 13:16:04
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Anja Becker
Anja Becker
Ulrich Meyer
Ulrich Meyer		Edit Dates
27.08.2003 17:11:42
09.05.2003 15:13:39
09.05.2003 11:58:59
19/08/2002 13:16:46
19/08/2002 13:16:04