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

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

URL of the conference:


URL for downloading the paper:


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
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
08/19/2002 01:16:04 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section