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

被引:14
作者
Berczi, Kristof [1 ]
Kobayashi, Yusuke [2 ]
机构
[1] Eotvos Lorand Univ, Dept Operat Res, Budapest, Hungary
[2] Univ Tokyo, Grad Sch Informat Sci & Technol, Dept Math Informat, Tokyo, Japan
基金
日本学术振兴会;
关键词
Connectivity augmentation; Square-free; 2-matching; Jump system; Subcubic graph; M-CONVEX FUNCTIONS; SMALLEST AUGMENTATION; DELTA-MATROIDS; EVEN FACTORS; T-MATCHINGS; CONNECTIVITY; GRAPH;
D O I
10.1016/j.jctb.2011.08.007
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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. (C) 2011 Elsevier Inc. All rights reserved.
引用
收藏
页码:565 / 587
页数:23
相关论文
共 56 条