Sparsification - a technique for speeding up dynamic graph algorithms Export

@article{citeulike:675266, 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.}, address = {New York, NY, USA}, author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Nissenzweig, Amnon}, citeulike-article-id = {675266}, citeulike-linkout-0 = {http://dx.doi.org/10.1145/265910.265914}, doi = {10.1145/265910.265914}, issn = {0004-5411}, journal = {J. ACM}, keywords = {2get, algorithms, graph-theory, link-analysis, optimization}, month = {September}, number = {5}, pages = {669--696}, posted-at = {2006-05-30 17:11:30}, priority = {2}, publisher = {ACM Press}, title = {Sparsification - a technique for speeding up dynamic graph algorithms}, url = {http://dx.doi.org/10.1145/265910.265914}, volume = {44}, year = {1997} }

TY - JOUR ID - citeulike:675266 L3 - citeulike-article-id:675266 N2 - 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. IS - 5 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 696 TI - Sparsification - a technique for speeding up dynamic graph algorithms PB - ACM Press VL - 44 SP - 669 KW - 2get KW - algorithms KW - graph-theory KW - link-analysis KW - optimization AU - Eppstein, David AU - Galil, Zvi AU - Italiano, Giuseppe AU - Nissenzweig, Amnon PY - 1997/09// UR - http://dx.doi.org/10.1145/265910.265914 ER -