David Eppstein
Giuseppe F. Italiano
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α(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α(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.
- ALBERTS, D., CATTANEO, G., AND ITALIANO, G. F. 1997. An empirical study of dynamic graph algorithms. ACM J. Exper. Algorithmics, to appear. Google Scholar
- AMATO, G., CATTANEO, G., AND ITALIANO, G.f. 1997. Experimental analysis of dynamic minimum spanning tree algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 314-323. Google Scholar
- BERMAN, A. M., PAULL, M. C., AND RYDER, B. G. 1990. Proving relative lower bounds for incremental algorithms. Acta Inf. 27, 665-683. Google Scholar
- CHERIYAN, J., KAO, M. Y., AND THURIMELLA, R. 1993. Scan-first search and sparse certificates-An improved parallel algorithm for k-vertex connectivity. SIAM J. Comput. 22, 157-174. Google Scholar
- CHERIYAN, J., AND THURIMELLA, R. 1991. Algorithms for parallel k-vertex connectivity and sparse certificates. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 391-401. Google Scholar
- DI BATTISTA, G., AND TAMASSIA, R. 1990. On-line graph algorithms with SPQR-trees. In Proceedings of the 17th International Collquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 443. Springer-Verlag, Berlin, Germany, pp. 598-611. Google Scholar
- DIETZ, P., AND SLEATOR, D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 365-372. Google Scholar
- DIXON, B., RAUCH, M., AND TARJAN, R.E. 1992. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput., 1184-1192. Google Scholar
- EPPSTEIN, D. 1992. Finding the k smallest spanning trees. BIT 32, 237-248. Google Scholar
- EPPSTEIN, D. 994a. Offiine algorithms for dynamic minimum spanning tree problems. J. Algor. 17, 237-250. Google Scholar
- EPPSTEIN, D. 1994b. Tree-weighted neighbors and geometric k smallest spanning trees. Int. J. Comput. Geom. Appl. 4, 229-238.Google Scholar
- EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND SPENCER, T.H. 1996. Separator based sparsification I. Planarity testing and minimum spanning trees. J. Comput. Syst. Sci, 52, 1 (Feb.), 3-27. Google Scholar
- EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND SPENCER, T.H. 1998. Separator based sparsification II. Planarity testing and minimum spanning trees. SIAM J. Comput., to appear. Google Scholar
- EPPSTEIN, D., ITALIANO, G. F., TAMASSIA, R., TARJAN, R. E., WESTBROOK, J., AND YUNG, M. 1992. Maintenance of a minimum spanning forest in a dynamic plane growth. J. Algor. 13, 33-54. Google Scholar
- FEDER, T., AND MIHAIL, M. 1992. Balanced matroids. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 26 -38. Google Scholar
- FERNANDEZ-BACA, D., SLUTZKI, G., AND EPPSTEIN, D. 1996. Using sparsification for parametric minimum spanning tree problems. Nordic J. Comput. 3, 4 (Winter), 352-366 (Special issue for the 5th SWAT). Google Scholar
- FREDERICKSON, G. N. 1985. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14, 781-798.Google Scholar
- FREDERICKSON, G. N. 1997. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26, 2 (Apr.), 484-538. Google Scholar
- FREDERICKSON, G. N., AND SRINIVAS, M.A. 1989. Algorithms and data structures for an expanded family of matroid intersection problems. SIAM J. Comput. 18, 112-138. Google Scholar
- FREDMAN, M. L., AND HENZIGER, M. R. 1997. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica, to appear.Google Scholar
- GABOW, H. N. 1991a. Applications of a poset representation to edge connectivity and graph rigidity. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 812-821. Google Scholar
- GABOW, H.N. 1991b. A matroid approach to finding edge connectivity and packing arborescenes. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 112-122. Google Scholar
- GABOW, H. N., AND STALLMAN, M. 1985. Efficient algorithms for graphic matroid intersection and parity. In Proceedings of the 12th International Colloquium of Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 194. Springer-Verlag, Berlin, Germany, pp. 339-350. Google Scholar
- GALIL, Z., AND ITALIANO, G.F. 1991a. Fully dynamic algorithms for 3-edge-connectivity. Unpublished manuscript.Google Scholar
- GALIL, Z., AND ITALIANO, G.F. 1991b. Maintaining biconnected components of dynamic planar graphs. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 510. Springer-Verlag, Berlin, Germany, pp. 339-350. Google Scholar
- GALIL, Z., AND ITALIANO, G.f. 1991c. Reducing edge connectivity to vertex connectivity. Sigact News 22, 57-61. Google Scholar
- GALIL, Z., AND ITALIANO, G. F. 1992. Fully dynamic algorithms for 2-edge-connectivity. SIAM J. Comput. 21, 1047-1069. Google Scholar
- GALIL, Z., AND ITALIANO, G.F. 1993. Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22, 11-28. Google Scholar
- HAN, X., KELSEN, P., RAMACHANDRAN, V., AND TARJAN, R.E. 1995. Computing minimal spanning subgraphs in linear time. SIAM J. Comput. 24, 1332-1358. Google Scholar
- HARARY, f. 1969. Graph Theory. Addison-Wesley, Reading, Mass.Google Scholar
- HENZINGER, M. R., AND KING, V. 1995a. Fully dynamic biconnectivity and transitive closure. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science. IEEE, New York. Google Scholar
- HENZINGER, M. R., AND KING, V. 1995b. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 519-527. Google Scholar
- HENZINGER, M. R., AND KING, V. 1997. Maintaining minimum spanning trees in dynamic graphs. In Proceedings of the 24th International Colloquium Automata, Languages, and Programming. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany. Google Scholar
- HENZINGER, M. R., AND LA POUTRt#, J.A. 1995. Certificates and fast algorithms for biconnectivity in fully dynamic graphs. In Proceedings of the 3rd European Symposium on Algorithms. Google Scholar
- HOPCROFT, J., AND TARJAN, R.E. 1973. Dividing a graph into triconnected components. SIAM J. Comput. 2, 135-158.Google Scholar
- KANEVSKY, A., TAMASSIA, R., DI BATTISTA, G., AND CHEN, J. 1991. On-line maintenance of the four-connected components of a graph. In Proceedings of the 32nd IEEE Symposium Foundations of Computer Science. IEEE, New York, pp. 793-801. Google Scholar
- KARGER, D. R., KLEIN, P. N., AND TARJAN, R.E. 1995. A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 321-328. Google Scholar
- KHANNA, S., MOTWANI, R., AND WILSON, R.H. 1996. On certificates and lookahead on dynamic graph problems. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (Atlanta, Ga., Jan. 28-30). ACM, New York, pp. 222-231. Google Scholar
- KING, V. 1995. A simpler minimum spanning tree verification algorithm. In Proceedings of the 4th Workshop Algorithms and Data Structures. pp. 440-448. Google Scholar
- LA POUTRI#, J. A. 1991. Dynamic graph algorithms and data structures. Ph.D. Dissertation. Department of Computer Science, Utrecht Univ.Google Scholar
- LAWLER, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart and Winston, New York.Google Scholar
- 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.Google Scholar
- RAUCH, M.H. 1995. Fully dynamic biconnectivity in graphs. Algorithmica 13, 6 (June), 503-538.Google Scholar
- SLEATOR, D. D., AND TARJAN, R.E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 24, 362-381. Google Scholar
- TARJAN, R.E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1,146-160.Google Scholar
- THURIMELLA, R. 1989. Techniques for the design of parallel graph algorithms. Ph.D. Dissertation. Univ. Texas, Austin, Austin, Tex. Google Scholar
- WESTBROOK, J., AND TARJAN, R.E. 1992. Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464.Google Scholar
Index Terms
- Sparsification—a technique for speeding up dynamic graph algorithms
Recommendations
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for ...
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or ...
Sparsification-a technique for speeding up dynamic graph algorithms
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer ScienceThe authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n))...
Reviews
William Fennell Smyth
As the authors observe, “graph algorithms are fundamental in computer science,” and therefore, so are the data structures that facilitate them. This paper introduces a data structure called a sparsification tree, which allows important features of undirected graphs—minimum spanning trees, vertex connectivity, edge connectivity, and bipartiteness—to be maintained dynamically (that is, in the face of updates to the graph) and more efficiently than in earlier approaches. Essentially the same unified approach is shown to apply to all the features noted, and the speedup is significant, in most cases replacing dependence on the number of edges by dependence only on the number of vertices, a replacement suggested by the term “sparsification.” The basic idea is simple: the vertices of the graph are partitioned into a balanced binary tree, which is then used as a basis for partitioning the edges into a balanced tree structure called the sparsification tree. It turns out that these two trees can be maintained under insertion and deletion of vertices and edges with efficient use of time and space, and therefore, so can many features derived from them. Furthermore, the authors claim that maintaining these data structures is practical, even for small graphs, with low constants of proportionality. This research represents a significant step forward in graph algorithms. The paper is well organized and, for an expert audience, reasonably well written. However, there are a number of minor inaccuracies, and some infelicities of terminology or style that would have been easier to interpret had a few simple examples been provided; the paper contains no examples whatsoever. The lemmas and theorems are not always stated precisely enough, and although the proofs are plausible, I did not always find them to be rigorous.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments