An algorithm for (n− 3)-connectivity augmentation problem: Jump system approach

K Bérczi, Y Kobayashi - Journal of Combinatorial Theory, Series B, 2012 - Elsevier
Journal of Combinatorial Theory, Series B, 2012Elsevier
We consider the problem of making a given (k− 1)-connected graph k-connected by adding
a minimum number of new edges, which we call the k-connectivity augmentation problem. In
this paper, we deal with the problem when k= n− 3 where n is the number of vertices of the
input graph. By considering the complement graph, the (n− 3)-connectivity augmentation
problem can be reduced to the problem of finding a maximum square-free 2-matching in a
simple graph with maximum degree at most three. We give a polynomial-time algorithm to …
We consider the problem of making a given (k−1)-connected graph k-connected by adding a minimum number of new edges, which we call the k-connectivity augmentation problem. In this paper, we deal with the problem when k=n−3 where n is the number of vertices of the input graph. By considering the complement graph, the (n−3)-connectivity augmentation problem can be reduced to the problem of finding a maximum square-free 2-matching in a simple graph with maximum degree at most three. We give a polynomial-time algorithm to find a maximum square-free 2-matching in a simple graph with maximum degree at most three, which yields a polynomial-time algorithm for the (n−3)-connectivity augmentation problem. Our algorithm is based on the fact that the square-free 2-matchings are endowed with a matroid structure called a jump system. We also show that the weighted (n−3)-connectivity augmentation problem can be solved in polynomial time if the weights are induced by a function on the vertex set, whereas the problem is NP-hard for general weights.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果