A Simplified Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints

Abstract

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by Givena multigraph G = (V,E) and a bipartition ? = {V_B,V_W} of V with V_B ? V_W = ?, find an edge set E of minimum size, consisting of edges that connect V_B and V_W, such that G_f = (V, E ? E_f) is k-edge-connected, where a multigraph means a graph, with unweighted edges, such that multiple edges may exist. In this paper, we give a simplified algorithm for finding an optimal solution to (? + 1)ECABP in O(|V||E| + |V|² log |V|) time when G is ?-edge-connected (? > 0), and show that the problem can be solved in linear time when 1 ? ? ? 2. The time complexity of the proposed algorithm is equal to that of an existing algorithm of Oki et al. (2012) (to appear).