Sparsification—a technique for speeding up dynamic graph algorithms

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.

REFERENCES

• 1: David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Journal of Experimental Algorithmics (JEA), 2, p.5-es, 1997 [doi>10.1145/264216.264223]
• 2: Giuseppe Amato , Giuseppe Cattaneo , Giuseppe F. Italiano, Experimental analysis of dynamic minimum spanning tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.314-323, January 05-07, 1997, New Orleans, Louisiana, United States
• 3: A. Michael Berman , Marvin C. Paull , Barbara G. Ryder, Proving relative lower bounds for incremental algorithms, Acta Informatica, v.27 n.7, p.665-683, 1990
• 4: Joseph Cheriyan , Ming-Yang Kao , Ramakrishna Thurimella, Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity, SIAM Journal on Computing, v.22 n.1, p.157-174, Feb. 1993 [doi>10.1137/0222013]
• 5: Joseph Cheriyan , Ramakrishna Thurimella, Algorithms for parallel k-vertex connectivity and sparse certificates, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.391-401, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103460]
• 6: Giuseppe Di Battista , Roberto Tamassia, On-line graph algorithms with SPQR-trees, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.598-611, July 1990, Warwick University, England
• 7: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 8: Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
• 9: David Eppstein, Finding the k smallest spanning trees, BIT, v.32 n.2, p.237-248, 1992 [doi>10.1007/BF01994879]
• 10: David Eppstein, Offline algorithms for dynamic minimum spanning tree problems, Journal of Algorithms, v.17 n.2, p.237-250, Sept. 1994 [doi>10.1006/jagm.1994.1033]
• 11: EPPSTEIN, D. 1994b. Tree-weighted neighbors and geometric k smallest spanning trees. Int. J. Comput. Geom. Appl. 4, 229-238.
• 12: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification I.: planarity testing and minimum spanning trees, Journal of Computer and System Sciences, v.52 n.1, p.3-27, Feb. 1996 [doi>10.1006/jcss.1996.0002]
• 13: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification I.: planarity testing and minimum spanning trees, Journal of Computer and System Sciences, v.52 n.1, p.3-27, Feb. 1996 [doi>10.1006/jcss.1996.0002]
• 14: David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook, Maintenance of a minimum spanning forest in a dynamic plane graph, Journal of Algorithms, v.13 n.1, p.33-54, March 1992 [doi>10.1016/0196-6774(92)90004-V]
• 15: Tomás Feder , Milena Mihail, Balanced matroids, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.26-38, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129716]
• 16: David Fernández-Baca , Giora Slutzki , David Eppstein, Using sparsification for parametric minimum spanning tree problems, Nordic Journal of Computing, v.3 n.4, p.352-366, Winter 1996
• 17: FREDERICKSON, G. N. 1985. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14, 781-798.
• 18: Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
• 19: Greg N. Frederickson , Mandayam A. Srinivas, Algorithms and data structures for an expanded family of matroid intersection problems, SIAM Journal on Computing, v.18 n.1, p.112-138, Feb. 1989 [doi>10.1137/0218008]
• 20: FREDMAN, M. L., AND HENZIGER, M. R. 1997. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica, to appear.
• 21: Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
• 22: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
• 23: Harold N. Gabow , Matthias Stallmann, Efficient Algorithms for Graphic Intersection and Parity (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.210-220, July 15-19, 1985
• 24: GALIL, Z., AND ITALIANO, G.F. 1991a. Fully dynamic algorithms for 3-edge-connectivity. Unpublished manuscript.
• 25: Zvi Galil , Giuseppe F. Italiano, Maintaining biconnected components of dynamic planar graphs (extended abstract), Proceedings of the 18th international colloquium on Automata, languages and programming, p.339-350, June 1991, Madrid, Spain
• 26: Zvi Galil , Giuseppe F. Italiano, Reducing edge connectivity to vertex connectivity, ACM SIGACT News, v.22 n.1, p.57-61, Winter 1991 [doi>10.1145/122413.122416]
• 27: Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for 2-edge connectivity, SIAM Journal on Computing, v.21 n.6, p.1047-1069, Dec. 1992 [doi>10.1137/0221062]
• 28: Zvi Galil , Giuseppe F. Italiano, Maintaining the 3-edge-connected components of a graph on-line, SIAM Journal on Computing, v.22 n.1, p.11-28, Feb. 1993 [doi>10.1137/0222002]
• 29: Xiaofeng Han , Pierre Kelsen , Vijaya Ramachandran , Robert Tarjan, Computing Minimal Spanning Subgraphs in Linear Time, SIAM Journal on Computing, v.24 n.6, p.1332-1358, Dec. 1995 [doi>10.1137/S0097539791224509]
• 30: HARARY, f. 1969. Graph Theory. Addison-Wesley, Reading, Mass.
• 31: M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
• 32: Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225269]
• 33: Monika Rauch Henzinger , Valerie King, Maintaining Minimum Spanning Trees in Dynamic Graphs, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.594-604, July 07-11, 1997
• 34: Monika Rauch Henzinger , Johannes A. La Poutré, Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.171-184, September 25-27, 1995
• 35: HOPCROFT, J., AND TARJAN, R.E. 1973. Dividing a graph into triconnected components. SIAM J. Comput. 2, 135-158.
• 36: Arkady Kanevsky , Roberto Tamassia , Giuseppe Di Battista , Jianer Chen, On-line maintenance of the four-components of a graph (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.793-801, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185451]
• 37: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 38: Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
• 39: Valerie King, A Simpler Minimum Spanning Tree Verification Algorithm, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.440-448, August 16-18, 1995
• 40: LA POUTRI#, J. A. 1991. Dynamic graph algorithms and data structures. Ph.D. Dissertation. Department of Computer Science, Utrecht Univ.
• 41: LAWLER, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart and Winston, New York.
• 42: NAGAMOCHI, H., AND IBARAKI, T. 1992. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 583-596.
• 43: RAUCH, M.H. 1995. Fully dynamic biconnectivity in graphs. Algorithmica 13, 6 (June), 503-538.
• 44: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 45: TARJAN, R.E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1,146-160.
• 46: Ramakrishna Thurimella , Donald S. Fussell, Techniques for the design of parallel graph algorithms, 1989
• 47: WESTBROOK, J., AND TARJAN, R.E. 1992. Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance

Keywords:
dynamic graph algorithms, edge and vertex connectivity, minimum spanning trees