On-line maintenance of triconnected components with SPQR-trees |
| |
Authors: | G Di Battista R Tamassia |
| |
Affiliation: | (1) Dipartimento di Discipline Scientifiche, Sezione Informatica, Terza Università di Roma, Via della Vasca Navale 84, 00146 Roma, Italy;(2) Department of Computer Science, Brown University, 02912-1910 Providence, RI, USA |
| |
Abstract: | We consider the problem of maintaining on-line the triconnected components of a graphG. Letn be the current number of vertices ofG. We present anO(n)-space data structure that supports insertions of vertices and edges, and queries of the type “Are there three vertex-disjoint paths between verticesv 1 andv 2?” A sequence ofk operations takes timeO(k·α(k, n)) ifG is biconnected(α(k, n) denotes the well-known Ackermann's function inverse), and timeO(n logn+k) ifG is not biconnected. Note that the bounds do not depend on the number of edges ofG. We use theSPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and theBC-tree, which represents the decomposition of a connected graph with respect to its biconnected components. |
| |
Keywords: | Vertex connectivity Dynamic algorithm Dynamic data structure Graph decomposition Triconnected components Network reliability |
本文献已被 SpringerLink 等数据库收录! |
|