We provide data structures 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 time O(n1/2) per change; 3-edge connectivity, in time O(n2/3) per change; 4-edge connectivity, in time O(na(n)) per change; k-edge connectivity for constant k, in time O(nlogn) per change; 2-vertex connectivity, and 3-vertex connectivity, in time O(n) per change; and 4-vertex connectivity, in time O(na(n)) per change.
Sparsification: A technique for speeding up dynamic graph algorithms / Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Nissenzweig, A.. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - 44:5(1997), pp. 669-696. [10.1145/265910.265914]
Sparsification: A technique for speeding up dynamic graph algorithms
ITALIANO G;
1997
Abstract
We provide data structures 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 time O(n1/2) per change; 3-edge connectivity, in time O(n2/3) per change; 4-edge connectivity, in time O(na(n)) per change; k-edge connectivity for constant k, in time O(nlogn) per change; 2-vertex connectivity, and 3-vertex connectivity, in time O(n) per change; and 4-vertex connectivity, in time O(na(n)) per change.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
