Heuristics for semi-external depth first search on directed graphs
Published 10 August 2002
Jop F. Sibeyn, James Abello, Ulrich Meyer
Citations33
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A set of heuristics is developed which together allow the performance of semi-external DFS for directed graphs in practice, and is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.
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 large 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.
Keywords
Computer Science
Medical Entomology and ZoologyThe Probabilistic Method
4,356 Citations1991Joel Spencer
A particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets - is explored.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
Journal of the ACMSelf-adjusting binary search trees
1,241 Citations1985Daniel D. Sleator, Robert E. Tarjan
The splay tree, a self-adjusting form of binary search tree, is developed and analyzed and is found to be as efficient as balanced trees when total running time is the measure of interest.
Communications of the ACMThe input/output complexity of sorting and related problems
1,240 Citations1988Alok Aggarwal, Jeffrey,S. Vitter
Tight upper and lower bounds are provided for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition.
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
The Steiner Tree Problem
860 Citations1992Frank K. Hwang, Dana Richards +1 more
Symposium on Discrete AlgorithmsExternal-memory graph algorithms
277 Citations1995Yi‐Jen Chiang, Michael T. Goodrich +4 more
A collection of new techniques for designing and analyzing external-memory algorithms for graph problems and illustrating how these techniques can be applied to a wide variety of speci c problems are presented.
NetworksSolving Steiner tree problems in graphs to optimality
247 Citations1998Thorsten Koch, Alexander Martín
The implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics is presented.
Improved algorithms and data structures for solving graph problems in external memory
127 Citations2002V. Krishna Kumar, Eric J. Schwabe
This paper presents I/O-efficient analogues of well-known data structures that are shown to be useful for obtaining simpler and improved algorithms for several graph problems.
Symposium on Discrete AlgorithmsOn external memory graph traversal
110 Citations2000Adam L. Buchsbaum, Michael H. Goldwasser +2 more
A new external memory data structure, the buffered repository tree, is described, and it is used to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an improved external algorithms for directed depth- first search.
Discrete Applied MathematicsImproved algorithms for the Steiner problem in networks
87 Citations2001Tobias Polzin, Siavash Vahdati Daneshmand
Several new techniques for dealing with the Steiner problem in (undirected) networks are presented, including heuristics that achieve sharper upper bounds than the strongest known heuristic for this problem despite running times which are smaller by orders of magnitude.
A random NC algorithm for depth first search
69 Citations1987Alok Aggarwal, Richard Anderson
This paper presents a fast parallel algorithm for constructing a depth first search tree for an undirected graph using a polynomial number of processors on a P-RAM.
Lecture notes in computer scienceA General Model of Undirected Web Graphs
56 Citations2001Colin Cooper, Alan Frieze
A general model of a random graph process whose degree sequence obeys a power law, which has recently been observed in graphs associated with the world wide web, is described.
COMBINATORICAA random 1-011-011-01algorithm for depth first search
41 Citations1988Alok Aggarwal, Richard Anderson
A fast parallel algorithm for constructing a depth first search tree for an undirected graph that runs in polylog time using a polynomial number of processors on aP-RAM.
Lecture notes in computer scienceRandom Geometric Problems on [0, 1]2
37 Citations1998Josep Dı́az, Jordi Petit +1 more
This paper presents some heuristics for the problem of the Minimal linear arrangement on [0,1]2 and concludes with a collection of open problems for graphs on random geometric models.
Lecture notes in computer scienceExternal Memory Algorithms for Outerplanar Graphs
34 Citations1999Anil Maheshwari, Norbert Zeh
This work presents external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth- first search (DFS) in outerplanAR graphs, and finding a 2/3-separator of size 2 for a given outerplanars graph.
Symposium on Discrete AlgorithmsI/O-optimal algorithms for planar graphs using separators
33 Citations2002Anil Maheshwari, Norbert Zeh
An I/O-efficient algorithm for computing a small vertex separator of an unweighted planar graph, superior to all existing external memory algorithms for this problem, as it requires neither a breadth-first search tree nor an embedding of the graph as part of the input.
I/O-efficient algorithms for graphs of bounded treewidth
25 Citations2001Anil Maheshwari, Norbert Zeh
External memory BFS on undirected graphs with bounded degree
5 Citations2001Ulrich Meyer
The first external memory algorithm for breadth-first search (BFS) is given which achieves I/ Os I/Os on arbitrary undirected graphs with n nodes and maximum node degree .
Average case analysis of graph-searching algorithms
5 Citations1990Robert Sedgewick, Sarantos Kapidakis
Coculture studies using preimplantation embryos in media conditioned on two types of kidney epithelial cells, finding different cells in contact with different types of medium show variability in the pattern of responses, highlighting the presence of false positives in coculture studies.