TY - GEN
T1 - External-memory graph algorithms
AU - Chiang, Yi Jen
AU - Goodrich, Michael T.
AU - Grove, Edward F.
AU - Tamassia, Roberto
AU - Vengroff, Darren Erik
AU - Vitter, Jeffrey Scott
N1 - Funding Information:
ttsupported in part by the U.S. Army Research Office under grant DAAL03-91-G-0035 and by the National Science Foundation under grant DMR-9217290.
Funding Information:
*Supported in part by the National Science Foundation, by the U.S. Army Research Office, and by the Advanced Research Projects Agency.
Funding Information:
5Supported in part by the National Science Foundation grants CCR-9003299, IRI-9116843, and CCR-9300079.
Funding Information:
ttSupported in part by the National Science Foundation under grant CCR-9007851 and by the U.S. Army Research Office under grants DAAL03-91-G-0035 and DAAH04-93-G-0076.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 1995/1/22
Y1 - 1995/1/22
N2 - We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of specific problems. Our results include: • Proximate-neighboring. We present a simple method for deriving external-memory lower bounds via reductions from a problem we call the "proximate neighbors" problem. We use this technique to derive non-trivial lower bounds for such problems as list ranking, expression tree evaluation, and connected components. • PRAM simulation. We give methods for efficiently simulating PRAM computations in external memory, even for some cases in which the PRAM algorithm is not work-optimal. We apply this to derive a number of optimal (and simple) external-memory graph algorithms. • Time-forward processing. We present a general technique for evaluating circuits (or "circuit-like" computations) in external memory. We also use this in a deterministic list ranking algorithm. • Deterministic 3-coloring of a cycle. We give several optimal methods for 3-coloring a cycle, which can be used as a subroutine for finding large independent sets for list ranking. Our ideas go beyond a straightforward PRAM simulation, and may be of independent interest. • External depth-first search. We discuss a method for performing depth first search and solving related problems efficiently in external memory. Our technique can be used in conjunction with ideas due to Ullman and Yannakakis in order to solve graph problems involving closed semi-ring computations even when their assumption that vertices fit in main memory does not hold. Our techniques apply to a number of problems, including list ranking, which we discuss in detail, finding Euler tours, expression-tree evaluation, centroid decomposition of a tree, least-common ancestors, minimum spanning tree verification, connected and biconnected components, minimum spanning forest, ear decomposition, topological sorting, reachability, graph drawing, and visibility representation.
AB - We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of specific problems. Our results include: • Proximate-neighboring. We present a simple method for deriving external-memory lower bounds via reductions from a problem we call the "proximate neighbors" problem. We use this technique to derive non-trivial lower bounds for such problems as list ranking, expression tree evaluation, and connected components. • PRAM simulation. We give methods for efficiently simulating PRAM computations in external memory, even for some cases in which the PRAM algorithm is not work-optimal. We apply this to derive a number of optimal (and simple) external-memory graph algorithms. • Time-forward processing. We present a general technique for evaluating circuits (or "circuit-like" computations) in external memory. We also use this in a deterministic list ranking algorithm. • Deterministic 3-coloring of a cycle. We give several optimal methods for 3-coloring a cycle, which can be used as a subroutine for finding large independent sets for list ranking. Our ideas go beyond a straightforward PRAM simulation, and may be of independent interest. • External depth-first search. We discuss a method for performing depth first search and solving related problems efficiently in external memory. Our technique can be used in conjunction with ideas due to Ullman and Yannakakis in order to solve graph problems involving closed semi-ring computations even when their assumption that vertices fit in main memory does not hold. Our techniques apply to a number of problems, including list ranking, which we discuss in detail, finding Euler tours, expression-tree evaluation, centroid decomposition of a tree, least-common ancestors, minimum spanning tree verification, connected and biconnected components, minimum spanning forest, ear decomposition, topological sorting, reachability, graph drawing, and visibility representation.
UR - http://www.scopus.com/inward/record.url?scp=84994666437&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994666437&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84994666437
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 139
EP - 149
BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PB - Association for Computing Machinery
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Y2 - 22 January 1995 through 24 January 1995
ER -