Monika R. Henzinger
Valerie King
Abstract
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 deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.
Let n denote the number of nodes in the graph. For a sequence of Ω(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.
- ALBERTS, D., AND HENZINGER, M.R. 1998. Average case analysis of dynamic graph algorithms. Algorithmica 20, 1, 32- 60.Google Scholar
- EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND NISSENZWEIG, A. 1997. Sparsification-A technique for speeding up dynamic graph algorithms. J. ACM 44, 5 (Sept.), 669-696. Google Scholar
- EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND SPENCER, W. 1996. Separator based sparsification for dynamic planar graph algorithms. J. Comput. Syst. Sci. 52, 1, 3-27. 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 planar graph. In J. Algorithms 13, 33-54. Google Scholar
- EVEN, S., AND SHILOACH, Y. 1981. An on-line edge-deletion problem. J. ACM 28, 1 (Jan.), 1-4. 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, 484-538. Google Scholar
- GALIL, Z., AND ITALIANO, G. f. 1992. Fully dynamic algorithms for 2-edge connectivity. SIAM J. Comput. 21, 1047-1069. Google Scholar
- HENZINGER, M.R. 1995. Fully dynamic biconnectivity in graphs. Algorithmica 13, 503-538.Google Scholar
- HENZINGER, M.R. 1999. Improved data structures for fully dynamic biconnectivity in graphs. SIAM J. Comput., to appear. Google Scholar
- HENZINGER, M. R. 1994.Fully dynamic cycle-equivalence in graphs. In Proceedings of the 35th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 744-755.Google Scholar
- HENZINGER, M. R., AND FREDMAN, M. L. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22, 351-362.Google Scholar
- HENZINGER, M. R., AND LA POUTRt#, H. 1995. Sparse certificates for dynamic biconnectivity in graphs. In Proceedings of the 3rd European Symposium on Algorithms. Springer-Verlag, Berlin, Germany, pp. 171-184. Google Scholar
- HENZINGER, M. R., AND THORUP, M. 1997. Improved sampling with applications to dynamic graph algorithms. Rand. Struct. Algor. 11, 4, 369-379. Google Scholar
- HOLM, J., DE LICHTENBERG, K., AND THORUP, M. 1998. Poly-logarithmic deterministic fullydynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In Proceedings of the 30th Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 79-89. Google Scholar
- MILTERSEN, P. B., SUBRAMANIAN, S., fITTER, J. S., AND TAMASSIA, R. 1994. Complexity models for incremental computation. Theoret. Comput. Science 130, 203-236. 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
- SLEATOR, D. D., AND TARJAN, R.E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 24, 362-381. Google Scholar
- SPIRA, P. M., AND PAN, A. 1975. On finding and updating spanning trees and shortest paths. SIAM J. Comput. 4, 375-380.Google Scholar
- TARJAN, R. E., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862-874.Google Scholar
- WESTBROOK, J., AND TARJAN, R. E. 1989. Amortized analysis of algorithms for set union with backtracking. SIAM J. Comput. 18, 1-11. Google Scholar
Index Terms
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
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 ...
Sparsification—a technique for speeding up dynamic graph algorithms
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(n...
New deterministic approximation algorithms for fully dynamic matching
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of ComputingWe present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an αK ...
Reviews
Adam Drozdek
The authors present a technique for designing fully dynamic algorithms with polylogarithmic time per operation for dynamically testing several graph properties. The technique combines a new graph decomposition and randomization. The edges are partitioned into O log n levels in such a way that the edges from loosely connected parts are on higher levels than the edges from highly connected parts. For each level i , a forest is maintained with edges in levels ji . After deleting an edge on level i , the edges on level i are sampled to find with high probability an edge that reconnects the two subtrees or to learn, also with high probability, that the cut defined by the deleted edge is too sparse for level i . In the latter case, the edges on the cut are copied to the next level and the procedure is tried for this higher level. This technique is applied first to design a fully dynamic connectivity algorithm for which the amortized cost of update is O log 3 n . This is also the cost of the algorithm for testing biconnectivity. The connectivity algorithm is then adapted to yield other algorithms. They include an algorithm to maintain a minimum spanning tree with k different weights in O pk log 3 n time for p updates and an algorithm that, for a graph with weights between 1 and u , solves the 1+ e -approximation of the minimum spanning tree problem in O p log 3 n log u e amortized time for p updates.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments