On-Line Maintenance of the Four-Connected Components of a Graph* (Extended Abstract)
Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen · Foundations of Computer Science · 1991
Given a graph G with n vertices and m edges, a kconnectivity query for vertices v' and U'' of G asks whether there exist k disjoint paths between U' and U. Answering such queries has important applications to network reliability. In this paper we consider the problem of performing k-connectivity queries for k 5 4. First, we present a static data structure that answers such queries in 0(1) time. Next, we consider the problem of performing queries intermixed with on-line updates that insert vertices and edges. For triconnected graphs we give a dynamic data structure that supports queries and updates in time O(a(e,n)) amortized, where n is the current number of vertices of the graph and e is the total number of operations performed (a(!, n) denotes the slowly growing Ackermann's function inverse). For general graphs, a sequence of e operations takes total time O(n1ogn + e). AI1 of the above data structures use space O(n), proportional to the number of vertices of the graph. Our results also yield an eficient algorithm for testing whether graph G is four-connected that runs in O(n a(n, n) + m) time using O(n + m) space.