On-line maintenance of triconnected components with SPQR-trees
On-line maintenance of triconnected components with SPQR-trees
复制标题
使用 SPQR 树在线维护三元连接组件
作者：
G. Battista;R. Tamassia
我们考虑的问题，保持在线的三连通组件的图G。设n是G的当前顶点数。我们提出了一个O（n）空间的数据结构，支持插入的顶点和边缘，和查询的类型“有三个顶点不相交的vertexv1和v2之间的路径？”如果G是双连通的（α（k，n）表示著名的Ackermann函数的逆），k个运算的序列的时间为O（k·α（k，n）），如果G不是双连通的，时间为O（nlogn +k）.注意，边界不依赖于G的边数。我们使用的SPQR树，一个通用的数据结构，表示一个双连通图相对于其三连通组件的分解，和BC树，它表示一个连通图相对于其双连通组件的分解。
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 verticesv1 andv2?” 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.