%0 Journal Article %1 eppstein1997sparsificationmdasha %A Eppstein, David %A Galil, Zvi %A Italiano, Giuseppe F. %A Nissenzweig, Amnon %C New York, NY, USA %D 1997 %I ACM %J J. ACM %K algorithms connectivity dynamic_graphs graph_theory %N 5 %P 669--696 %R 10.1145/265910.265914 %T Sparsification -- a Technique for Speeding Up Dynamic Graph Algorithms %U http://doi.acm.org/10.1145/265910.265914 %V 44 %X 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(n2/3) per change; 4-edge connectivity, in time O(n&agr;(n)) per change; k-edge connectivity for constant k, in time O(nlogn) per change;2-vertex connectivity, and 3-vertex connectivity, in the O(n) per change; and 4-vertex connectivity, in time O(n&agr;(n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms.All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call sparsification.

@article{eppstein1997sparsificationmdasha, abstract = {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(n2/3) per change; 4-edge connectivity, in time O(n&agr;(n)) per change; k-edge connectivity for constant k, in time O(nlogn) per change;2-vertex connectivity, and 3-vertex connectivity, in the O(n) per change; and 4-vertex connectivity, in time O(n&agr;(n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms.All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call sparsification.}, acmid = {265914}, added-at = {2019-09-12T19:27:37.000+0200}, address = {New York, NY, USA}, author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Nissenzweig, Amnon}, biburl = {https://www.bibsonomy.org/bibtex/244f2d02b7882df95303a93877cfd296e/peter.ralph}, doi = {10.1145/265910.265914}, interhash = {3d37fabb81e36abd8838cdce57bbfa22}, intrahash = {44f2d02b7882df95303a93877cfd296e}, issn = {0004-5411}, issue_date = {Sept. 1997}, journal = {J. ACM}, keywords = {algorithms connectivity dynamic_graphs graph_theory}, month = sep, number = 5, numpages = {28}, pages = {669--696}, publisher = {ACM}, timestamp = {2019-09-12T19:27:37.000+0200}, title = {Sparsification -- a Technique for Speeding Up Dynamic Graph Algorithms}, url = {http://doi.acm.org/10.1145/265910.265914}, volume = 44, year = 1997 }