K-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
K-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
复制标题
任意多重图中的 K 边和 3 顶点连通性增强
DOI：
10.1007/3-540-49381-6_18
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
Toshimasa Ishii;H. Nagamochi;T. Ibaraki
给定一个无向多重图G =（V，E）和两个正整数l和k，边和点连通性扩充问题要求用最少的新边数扩充G，使得到的多重图成为l-边连通和k-点连通的.本文证明了对于任意的重图G，在a固定且k = 3的情况下，问题可以在多项式时间内求解
Given an undirected multigraph G = (V,E ) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting multigraph becomes l-edge-connected and k-vertex-connected. In this paper, we show that the problem with a fixed and k = 3 can be solved in polynomial time for an arbitrary multigraph G