A Functional Approach to External Graph Algorithms
Lecture notes in computer sciencePublished 1 January 1998
James Abello, Adam L. Buchsbaum, Jeffery Westbrook
Citations126
SJR quartileQ2
SJR score0.35
SNIP0.55
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.
Abstract
We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected components, minimum spanning trees, bottleneck minimum spanning trees, and maximal matchings in undirected graphs and multi-graphs. Our I/O bounds compete with those of previous approaches. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Proceedings of the American Mathematical SocietyOn the shortest spanning subtree of a graph and the traveling salesman problem
5,003 Citations1956Joseph B. Kruskal
Journal of Computer and System SciencesUniversal classes of hash functions
2,573 Citations1979J.Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
An introduction to parallel algorithms
1,602 Citations1992Joseph F. JáJá
This book provides an introduction to the design and analysis of parallel algorithms with special attention to the selection of relevant data structures and to algorithm design principles that have proved to be useful.
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.
SIAM Journal on ComputingA Simple Parallel Algorithm for the Maximal Independent Set Problem
1,134 Citations1986Michael Luby
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
Theoretical Computer ScienceDeforestation: transforming programs to eliminate trees
707 Citations1990Philip Wadler
The algorithm applies to any term containing only functions with definitions in a given syntactic form, and is suitable for incorporation in an optimizing compiler.
Making data structures persistent
700 Citations1986James R. Driscoll, Neil Sarnak +2 more
This paper develops simple, systematic, and efficient techniques for making linked data structures persistent, and uses them to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O (1) space bounds for insertion and deletion.
Libckpt: transparent checkpointing under Unix
579 Citations1995James S. Plank, Micah Beck +2 more
Journal of the ACMWorst-case Analysis of Set Union Algorithms
449 Citations1984Robert E. Tarjan, Jan Van Leeuwen
It is shown that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.
Journal of the ACMA randomized linear-time algorithm to find minimum spanning trees
404 Citations1995David R. Karger, Philip N. Klein +1 more
A randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights is presented, a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
Journal of the ACMSparsification—a technique for speeding up dynamic graph algorithms
290 Citations1997David Eppstein, Zvi Galil +2 more
All algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which is calledsparsification, and results speed up the insertion times to match the bounds of known partially dynamic algorithms.
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.
Journal of the ACMA fast parallel algorithm for the maximal independent set problem
274 Citations1985Richard M. Karp, Avi Wigderson
A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G and uses the “dynamic pigeonhole principle” that generalizes the conventional pigeon hole principle.
Information Processing LettersA fast and simple randomized parallel algorithm for maximal matching
227 Citations1986Amos Israeli, Alon Itai
A parallel randomized algorithm to find a maximal matching is presented that improves the best known deterministic algorithm by a factor of log 2 vbEvb.
Communications of the ACMEfficient parallel algorithms for some graph problems
207 Citations1982Francis Y. L. Chin, John Lam +1 more
A general time bound is derived for a parallel algorithm that uses K processors for finding the connected components of an undirected graph and the result is optimal in the sense that the speedup ratio is linear with the number of processors used.
Lecture notes in computer scienceThe buffer tree: A new technique for optimal I/O-algorithms
184 Citations1995Lars Arge
It is shown how the technique can be used to develop a search-tree-like structure, a priority-queue, a (one-dimensional) range-tree and a segment-tree, and examples of how these structures can be used to develop efficient I/O-algorithms.
I/O-complexity of graph algorithms
132 Citations1999Kameshwar Munagala, Abhiram Ranade
Lower bounds of Q( $ Sort(V)) are shown for the I/Ocomplexity of graph theoretic problems like connected components, biconnected components, and minimum spanning trees, where E and V are the number of edges and vertices in the input graph, respectively.
External memory algorithms
128 Citations1998Jeffrey Scott Vitter
This tutorial surveys the state of the art in the design and analysis of external memory algorithms (also known as EM algorithms or out-of-core algorithms or I/O algorithms), and discusses a variety of problems and shows how to solve them efficiently in external memory.
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.
Information Processing LettersThe min-max spanning tree problem and some extensions
122 Citations1978P. M. Camerini
Information Processing LettersAn improved parallel algorithm for maximal matching
117 Citations1986Amos Israeli, Yossi Shiloach
A parallel O(log 3 vbEvb) algorithm for finding a maximal matching in a graph G(V, E) is presented, and the model of computation is the CRCW-PRAM, and vbVvb + vb Evb processors are used.
Journal of the ACMProbabilistic recurrence relations
95 Citations1994Richard M. Karp
Several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of T(z) are given, and a number of typical applications of these bounds to the analysis of algorithms are presented.
The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract)
95 Citations1995Lars Arge
Annals of Mathematics and Artificial IntelligenceThe input/output complexity of transitive closure
60 Citations1991Jeffrey D. Ullman, Mihalis Yannakakis
The sparse case, it is shown that I/O equal toO(n2√e/s) is sufficient, although the algorithm proposed meets the definition of “standard” only if the underlying graph is acyclic, and the sparse/acyclic case, for standard algorithms is settled.
Efficient External-Memory Data Structures and Applications
46 Citations1996Lars Arge
This thesis develops a technique for transforming an internal memory tree data structure into an external data structure which can be used in a batched dynamic setting, and proves that the new ordered binary-decision diagram manipulation algorithms are asymptotically optimal among a class of algorithms that include all know manipulation algorithms.
Lecture notes in computer scienceWorst-case efficient external-memory priority queues
46 Citations1998Gerth Stølting Brodal, Jyrki Katajainen
A priority-queue implementation is given which is efficient with respect to the number of block transfers or I/Os performed between the internal and external memories of a computer.
BRICS Report SeriesThe Buffer Tree: A New Technique for Optimal I/O Algorithms
23 Citations1996Lars Arge
Dynamic and i/o-efficient algorithms for computational geometry and graph problems: theoretical and experimental results
18 Citations1996Yi‐Jen Chiang
An extensive experimental study comparing the practical I/Oiency of four algorithms for the orthogonal segment intersection problem with large-scale test data is presented, and the observed behavior of the algorithms is consistent with their theoretical properties.
Information Processing LettersAn optimal parallel algorithm for maximal matching
17 Citations1994Pierre Kelsen
This is the first deterministic algorithm for maximal matching that achieves a linear time-processor product and it is proved a general result linking the parallel complexity of maximal matching on bipartite graphs and general graphs.
Making workstations a friendly environment for batch jobs
5 Citations2003Miron Livny, Michael Litzkow
It is argued that batch processing is not something of the past or something which applies only to mainframe computers, but that distributed batch processing on workstations in an area of considerable and increasing importance, and as such should be given serious consideration by operating system designers.
Simple randomized parallel algorithms for finding a maximal matching in an undirected graph
2 Citations2002S.B. Yang, Sudarshan Dhall +1 more
The authors present simple randomized parallel algorithms for finding a maximal matching in a unidirectional graph G=(V, E) for the CRCW and CREW models, which has O(log m) expected running time using m processors.