Determining edge connectivity in 0(nm)
Determining edge connectivity in 0(nm)
复制标题
DOI：
10.1109/sfcs.1987.19
复制
发表时间：
1987-10
期刊：
影响因子：
--
通讯作者：
D. Matula
中科院分区：
文献类型：
--
作者：
D. Matula
我们描述了一个在O（nm）时间内确定n-顶点m-边图G的边连通度的算法。一个改进表明，一个图是否是k-边连通的问题可以在O（kn 2）中确定。对于满足m = Ω（n2）的稠密图，后一个结果意味着对于任意固定的k，判定一个图是否k-边连通可以在时间上与输入大小成线性关系.
We describe an algorithm that determines the edge connectivity of an n-vertex m-edge graph G in O(nm) time. A refinement shows that the question as to whether a graph is k-edge connected can be determined in O(kn2). For dense graphs characterized by m = Ω(n2), the latter result implies that determination of whether a graph is k-edge connected for any fixed k can be accomplished in time linear in input size.