2002 · 52 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsData StructuresTheory Of ComputationAlgorithm AnalysisComputational ComplexityDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsConnected Components MaintenanceConnectivity AlgorithmsDynamic Graph AlgorithmsDynamic Graph Data StructuresGraph Connectivity QueriesInverse Ackermann FunctionOnline Graph Algorithms
Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for k<or=4. First, they present a static data structure that answers such queries in O(1) time. Next, they consider the problem of performing queries intermixed with online updates that insert vertices and edges. For triconnected graphs they give a dynamic data structure that supports queries and updates in time O( alpha (l,n)) amortized, where n is the current number of vertices of the graph and l is the total number of operations performed ( alpha (l, n) denotes the slowly growing Ackermann function inverse). For general graphs, a sequence of l operations takes total time O(n log n+l). All of the above data structures use space O(n), proportional to the number of vertices of the graph. The results also yield an efficient algorithm for testing whether graph G is four-connected that runs in O(n alpha (n, n)+m) time using O(n+m) space.<<ETX>>
22
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Dividing a Graph into Triconnected Components
John E. Hopcroft, Robert E. Tarjan · SIAM Journal on Computing · 1973 · 841 citations
Worst-case Analysis of Set Union Algorithms
Robert E. Tarjan, Jan Van Leeuwen · Journal of the ACM · 1984 · 458 citations · Full text