Augmenting Edge-Connectivity over the Entire Range in Õ(nm) Time
Augmenting Edge-Connectivity over the Entire Range in Õ(nm) Time
复制标题
在 Õ(nm) 时间内增强整个范围的边缘连接
DOI：
10.1006/jagm.1998.0983
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
H. Nagamochi;T. Ibaraki
对于给定的无向图G =（V，E，cG），其边用非负实G：E？R+，让？G（k）表示使G是k-边连通所需的最小权值，G *（k）是由G得到的结果图。本文首先表明，功能？整个兰盖克？0，+∞]的时间复杂度为O（nm+ n2 logn），证明了G *（k）在整个区间上都可以由O（nlogn）个加权圈得到，且这些圈的时间复杂度为O（nm+ n2 logn），其中和分别为顶点数和边数.
For a given undirected graphG=(V,E,cG) with edges weighted by nonnegative realscG:E?R+, let ?G(k) stand for the minimum amount of weights which needs to be added to makeG k-edge-connected, and letG*(k) be the resulting graph obtained fromG. This paper first shows that function ?Gover the entire rangek?0,+∞] can be computed inO(nm+n2logn) time, and then shows that allG*(k) in the entire range can be obtained fromO(nlogn) weighted cycles, and such cycles can be computed inO(nm+n2logn) time, wherenandmare the numbers of vertices and edges, respectively.
H.NAGAMOCHI、T.LBARAKI：“一种用于查找 k 连接图的稀疏 k 连接生成子图的线性时间算法”Algorithmica。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--