Sparsification — A technique for speeding up dynamic graph algorithms

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig
Proc. 33rd Symp. Foundations of Computer Science, IEEE, Oct 1992, pp. 60–69
Tech. report RC 19272 (83907), IBM, T. J. Watson Research Ctr., 1993
J. ACM 44(5):669–696, Sep 1997
Tech. report CS96-10, Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata ed Informatica, Oct 1996
Mathematical Reviews 98k:68039
http://doi.acm.org/10.1145/265910.265914

Cited by:

• Bounded incremental computation
• A categorized bibliography on incremental computation
• Fully dynamic algorithms for bin packing: being (mostly) myopic helps
• Decremental 2- and 3-connectivity on planar graphs
• Fully dynamic algorithms for 2-edge-connectivity
• Combine and conquer: a general technique for dynamic algorithms
• Fast algorithms for dynamic 2-connectivity with backtracking
• Fully dynamic planarity testing in planar embedded graphs
• Fully Dynamic Graph Algorithms and their Data Structures
• Fully dynamic biconnectivity in graphs
• Improved data structures for fully dynamic biconnectivity
• Fully dynamic cycle-equivalence in graphs
• An $o(n)$ work EREW parallel algorithm for updating MST
• On the structure of DFS-forests on directed graphs and the dynamic maintenance of DFS on DAG's
• Maintaining the 4-edge-connected components of a graph on-line
• Using randomized sparsification to approximate minimum cuts
• Random sampling in cut, flow, and network design problems
• Dynamic algebraic algorithms
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Average case analysis of dynamic graph algorithms
• Data structures for two-edge connectivity in planar graphs
• Fully dynamic biconnectivity and transitive closure
• Optimal on-line search and sublinear time update in string matching
• Algorithms for all single deletions in a minimum spanning tree, simultaneously
• Fully dynamic transitive closure in plane dags with one source and one sink
• On mixed connectivity certificates
• A technique to speed up parallel fully dynamic algorithms for MST
• On certificates and lookahead in dynamic graph problems
• An empirical study of dynamic graph algorithms
• Improved sampling with applications to dynamic graph algorithms
• Output-sensitive reporting of disjoint paths
• On-line planar graph embedding
• On-line and dynamic algorithms for shortest path problems
• To provide or to bound: sampling in fully dynamic graph algorithms
• Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King
• Random Sampling in Graph Optimization Problems
• Experimental analysis of dynamic minimum spanning tree algorithms
• Decremental dynamic connectivity
• Maintaining minimum spanning trees in dynamic graphs
• Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees
• Dyn-FO: a parallel, dynamic complexity class
• Dynamic and static algorithms for optimal placement of resources in a tree
• Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation
• A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity
• Data structures
• Spanning tree algorithms for connectivity and routing in communications networks
• Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree
• Dynamically switching vertices in planar graphs
• Poly-logarithmic deterministic fully-dynamic graph algorithms II: 2-edge and biconnectivity
• Computing with time-varying data: Sequential complexity and parallel speed-up
• Average case analysis of fully dynamic reachability for directed graphs
• A flexible algorithm for generating all the spanning trees in undirected graphs
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Approximating minimum cuts under insertions
• Systematic derivation of incremental programs
• A software library of dynamic graph algorithms
• Poly-logarithmic deterministic fully-dynamic graph algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Dynamic Data Structures for String Matching Problems
• Maintaining spanning trees of small diameter
• Maintaining regular properties dynamically in $k$-terminal graphs
• Lower bounds for fully dynamic connectivity problems in graphs
• Fully dynamic algorithms for chordal graphs
• Efficient algorithms for Petersen's matching theorem
• An algorithm for enumerating all directed spanning trees in a directed graph
• Maintaining the classes of 4-edge-connectivity in a graph on-line
• A uniform approach to semi-dynamic problems on digraphs
• Kinetic connectivity of rectangles
• Batch dynamic algorithms for two graph problems
• Static and dynamic parallel computation of connected components
• Fully dynamic planarity testing with applications
• An efficient data structure for lattice operations
• Incremental Computation: A Semantics-Based Systematic Transformational Approach
• Decremental biconnectivity on planar graphs
• A fully dynamic algorithm for recognizing and representing proper interval graphs
• Fully sequential and distributed dynamic algorithms for minimum spanning trees
• Near-optimal fully-dynamic graph connectivity
• Maintenance of 2- and 3-edge-connected components of graphs II
• Implementation and experimental evaluation of graph connectivity algorithms using LEDA
• Dynamic graph algorithms{}
• Top-trees and dynamic graph algorithms
• Design and performance of convergence routing on multiple spanning trees
• An experimental study of polylogarithmic fully-dynamic connectivity algorithms
• Improved algorithms for point placement
• Efficiency by incrementalization: an introduction
• Dynamic graph algorithms with applications
• Multi-parameter minimum spanning trees
• Implementation of dynamic trees with in-subtree operations
• Implementations of dynamic tree collections based on splay trees
• An experimental study of dynamic algorithms for transitive closure
• A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
• Experimental analysis of dynamic algorithms for the single-source shortest path problem
• Notes on computing peaks in $k$-levels and parametric spanning trees
• External memory algorithms and data structures: dealing with massive data
• Fully-dynamic min-cut
• A functional approach to external graph algorithms
• Reconstructing a minimum spanning tree after deletion of any node
• Fully dynamic maintenance of $k$-connectivity in parallel
• Revised version of ”Efficient Cross-Trees for External Memory“
• Dynamic subgraph connectivity with geometric applications
• Decomposable multi-parameter matroid optimization problems
• Implementations and experimental studies of dynamic graph algorithms
• CATAI: Concurrent algorithms and data types animation over the Internet
• Maintaining dynamic minimum spanning trees: An experimental study
• External memory algorithms
• Fully dynamic algorithms for bounded genus graphs
• Maintaining information in fully-dynamic trees with top trees
• Identifying common connected components of graphs
• Incremental computation for transformational software development
• Quality of EDA CAD tools: definitions, metrics and directions
• Graph distances in the streaming model: the value of space
• $k$-connectivity in the semi-streaming model
• Faster dynamic matchings and vertex connectivity