Optimal Augmentation of a 2-Vertex-Connected Multigraph to an l-Edge-Connected and 3-Vertex-Connected Multigraph

摘要

Given an undirected multigraph G = (V, E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in O-tilde (mn~2) time for any fixed l and k = 3 if an input multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.