About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1992
Conference paper
Sparsification-a technique for speeding up dynamic graph algorithms
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(n1/2log(m/n)) per change; 3-edge-connectivity, in time O(n2/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.