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.
