Name
Abstract | ||
|---|---|---|
We give algorithms and data structures that maintain the 2-edge and 2-vertex-connected components of a graph under insertions and deletions of edges and vertices, where deletions occur in a backtracking fashion (i.e., deletions undo the insertions in the reverse order). Our algorithms run in $\Theta (\log n)$ worst-case time per operation and use $\Theta (n)$ space, where n is the number of vertices. Using our data structure we can answer queries, which ask whether vertices u and v belong to the same 2-connected component, in $\Theta (\log n)$ worst-case time. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1137/S0097539794272582 | SIAM J. Comput. |
Keywords | Field | DocType |
backtracking fashion,worst-case time,dynamic graph algorithms,reverse order,vertices u,2-connected component,log n,backtracking,2-vertex-connected component,data structure,connected component | Graph theory,Binary logarithm,Discrete mathematics,Data structure,Combinatorics,Tree (graph theory),Vertex (geometry),Vertex (graph theory),Backtracking,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 1 | 0097-5397 |
Citations | PageRank | References |
0 | 0.34 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes A. La Poutré | 1 | 308 | 24.78 |
| Jeffery Westbrook | 2 | 694 | 88.18 |