conference paper
Fully dynamic biconnectivity and transitive closure
published
yes
Monika H
Henzinger
author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530
V.
King
author
Foundations of Computer Science
This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log/sup 4/n). Only recently the best deterministic result for this problem was improved to O(/spl radic/nlog/sup 2/n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(nlog/sup 2/n).
Institute of Electrical and Electronics Engineers1995Milwaukee, WI, United States
eng
Proceedings of IEEE 36th Annual Foundations of Computer Science
0272-5428
0-8186-7183-110.1109/SFCS.1995.492668
664-672
yes
Henzinger MH, King V. Fully dynamic biconnectivity and transitive closure. In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 1995:664-672. doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>
Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, 664–72. Institute of Electrical and Electronics Engineers, 1995. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>.
Henzinger MH, King V. 1995. Fully dynamic biconnectivity and transitive closure. Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of Computer Science, 664–672.
M. H. Henzinger and V. King, “Fully dynamic biconnectivity and transitive closure,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee, WI, United States, 1995, pp. 664–672.
Henzinger, M. H., & King, V. (1995). Fully dynamic biconnectivity and transitive closure. In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i> (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>
M.H. Henzinger, V. King, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 1995, pp. 664–672.
Henzinger, Monika H., and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>.
116842022-07-28T11:28:13Z2023-02-09T11:35:17Z