Independence free graphs and vertex connectivity augmentation Bill Jackson ? and
Independence free graphs and vertex connectivity augmentation Bill Jackson ? and
复制标题
独立自由图和顶点连接增强比尔·杰克逊？
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
T. Jordán
中科院分区：
文献类型：
--
作者：
T. Jordán
给定一个无向图G和一个正整数k，k-点连通性扩充问题是寻找一个最小的新边集F，使G+F是k-点连通的。这个问题的多项式算法只在k ≤ 4时被发现，图连通性中的一个主要问题是这个问题是否在多项式时间内可解。在本文中，我们开发了一个算法，提供了一个最佳的解决方案，在多项式时间为每个固定的k。在最优解的大小大于k的情况下，我们还给出了最小增广集的大小的最小-最大公式。在我们的证明中的一个关键步骤是一个完整的解决方案的增强问题的一个新的家庭的图，我们称之为k-独立自由图。我们还证明了新的分裂定理的顶点连通性。
Given an undirected graph G and a positive integer k, the k-vertex-connectivity augmentation problem is to find a smallest set F of new edges for which G+F is k-vertex-connected. Polynomial algorithms for this problem have been found only for k ≤ 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general. In this paper we develop an algorithm which delivers an optimal solution in polynomial time for every fixed k. In the case when the size of an optimal solution is large compared to k, we also give a min-max formula for the size of a smallest augmenting set. A key step in our proofs is a complete solution of the augmentation problem for a new family of graphs which we call k-independence free graphs. We also prove new splitting off theorems for vertex connectivity.