Quasi-Fully Dynamic Algorithms for Two-Connectivity and Cycle Equivalence |
| |
Authors: | M R Korupolu V Ramachandran |
| |
Affiliation: | (1) Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712-1188, USA. {madhukar, vlr}@cs.utexas.edu., US;(2) Current address: Akamai Technologies, Inc., 201 Broadway, Cambridge, MA 02139, USA., US |
| |
Abstract: | We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms , which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms
are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic
updates occur on the remaining edges in the graph.
We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for 2-edge connectivity and O(log n) amortized time per operation for cycle equivalence. The former is deterministic while the latter is Monte-Carlo-type randomized.
For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log
3
n) amortized time per operation.
The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers)
is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is
known for this problem.
Received October 26, 1998; revised October 1, 1999, and April 15, 2001. |
| |
Keywords: | , Dynamic algorithms, Graph algorithms, Cycle equivalence, Connected graphs, Edge and vertex connectivity, Randomized,,,,,algorithms, Compiler optimization, |
本文献已被 SpringerLink 等数据库收录! |
|