Dividing a Graph into Triconnected Components

Dividing a Graph into Triconnected Components
复制标题

DOI：
10.1137/0202012
复制
发表时间：
1973-09
期刊：
SIAM J. Comput.
影响因子：
--
通讯作者：
J. Hopcroft;R. Tarjan
J. Hopcroft;R. Tarjan
中科院分区：
其他
文献类型：
--
作者：
J. Hopcroft;R. Tarjan

文献摘要

被引文献

相似文献

提出了一种将图划分为三连通分量的算法。当在随机存取计算机上实现时，该算法需要$O(V + E)$的时间和空间来分析一个具有$V$个顶点和$E$条边的图。该算法在理论上在常数因子范围内是最优的，并且在实践中是高效的。
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V + E)$ time and space to analyze a graph with V vertices and E edges. The algorithm is both theoretically optimal to within a constant factor and efficient in practice.