A Faster Edge Splitting Algorithm in Multigraphs and its Application to the Edge-Connectivity Augmentation Problem
A Faster Edge Splitting Algorithm in Multigraphs and its Application to the Edge-Connectivity Augmentation Problem
复制标题
多重图中更快的边缘分裂算法及其在边缘连通性增强问题中的应用
DOI：
10.1007/3-540-59408-6_68
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
H. Nagamochi;T. Ibaraki
本文首先表明，给定一个多重图G和一个偶数度的顶点，所有关联的边都可以在O(mn2+n2logn)时间内被分割掉（即，如果Gisk边连通，则生成的多重图也是k边连通的），其中n和m分别是G中顶点和边的数量。该算法的独特之处在于它不依赖于最大流量计算。基于此，我们证明，给定一个正整数k，通过添加最少数量的新边来建立多重图Gk边连接的问题可以在O(m+minen2+n3logn,kn3)时间内解决，其中(≤n2)是G之间有边的顶点对的数量。
This paper first shows that, given a multigraphGand a vertexswith even degree, all edges incident toscan be split off (i.e., ifGisk-edge-connected, then the resulting multigraph is alsok-edge-connected) inO(mn2+n2logn) time, wherenandmare the numbers of vertices and edges inG, respectively. This algorithm is unique in the sense that it does not rely on the maximum flow computations. Based on this, we then show that, given a positive integerk, the problem of making a multigraphGk-edge-connected by adding the smallest number of new edges can be solved inO(m+minen2+n3logn,kn3) time, wheree(≤n2) is the number of pairs of vertices between whichGhas an edge.
H.NAGAMOCHI、T.LBARAKI：“一种用于查找 k 连接图的稀疏 k 连接生成子图的线性时间算法”Algorithmica。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--