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.
Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Nissenzweig, A.. (1997). Sparsification: A technique for speeding up dynamic graph algorithms. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, (ISSN: 0004-5411), 44:5, 669-696. Doi: 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.
