Improved sparsification

David Eppstein, Zvi Galil, and Giuseppe F. Italiano
Tech. report 93-20, Univ. of California, Irvine, Dept. of Information and Computer Science, 1993
http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

Cited by:

• Fully dynamic cycle-equivalence in graphs
• An $o(n)$ work EREW parallel algorithm for updating MST
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Average case analysis of dynamic graph algorithms
• Fully dynamic biconnectivity and transitive closure
• A technique to speed up parallel fully dynamic algorithms for MST
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• An empirical study of dynamic graph algorithms
• Fast algorithms for $k$-shredders and $k$-node connectivity augmentation
• Improved sampling with applications to dynamic graph algorithms
• Fully dynamic biconnectivity in graphs
• Bounded incremental computation
• To provide or to bound: sampling in fully dynamic graph algorithms
• Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King
• Decremental dynamic connectivity
• Maintaining minimum spanning trees in dynamic graphs
• Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees
• Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation
• Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree
• Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems
• 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
• Batch dynamic algorithms for two graph problems
• Static and dynamic parallel computation of connected components
• Dynamic graph algorithms{}
• Fully dynamic maintenance of $k$-connectivity in parallel
• Fully dynamic algorithms for bounded genus graphs