Sparsification-a technique for speeding up dynamic graph algorithms
Author:
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 60-69
Abstract
The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification.Keywords
This publication has 19 references indexed in Scilit:
- Maintaining bridge-connected and biconnected components on-lineAlgorithmica, 1992
- Fully dynamic biconnectivity in graphs1992
- Reducing edge connectivity to vertex connectivityACM SIGACT News, 1991
- Fully dynamic algorithms for edge connectivity problems1991
- A matroid approach to finding edge connectivity and packing arborescences1991
- Algorithms for parallel k-vertex connectivity and sparse certificates1991
- Proving relative lower bounds for incremental algorithmsActa Informatica, 1990
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983