Sparsification-a technique for speeding up dynamic graph algorithms.

We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in timeO(n1/2) per change; 3-edge connectivity, in time O...

Full description

Bibliographic Details

Published in:	Journal of the ACM 44, 5 (1997).
Main Author:	Eppstein, David
Format:	Article
Language:	English
Subjects:	Mathematics of computing. Discrete mathematics. Graph theory. Graph algorithms. Theory of Computation. Analysis of algorithms and problem complexity. Algorithms. Performance.