Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Heuristics for Semi-External Depth First Search on Directed Graphs

Sibeyn, J. F., Abello, J., & Meyer, U. (2002). Heuristics for Semi-External Depth First Search on Directed Graphs. In SPAA 2002: Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (pp. 282-292). New York, USA: ACM.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sibeyn, Jop F., Autor
Abello, James, Autor
Meyer, Ulrich1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003-08-272002
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 201788
Anderer: Local-ID: C1256428004B93B8-31A8B545C99A2D37C1256C1A003DE57B-SiAbMe02
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: SPAA 2002
Veranstaltungsort: Winnipeg, Canada
Start-/Enddatum: 2002-08-11 - 2002-08-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 282 - 292 Identifikator: ISBN: 1-58113-529-7