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

Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe


The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by Givena multigraph G = (V,E) and a bipartition ? = {VB,VW} of V with VB ? VW = ?, find an edge set E of minimum size, consisting of edges that connect VB and VW, such that Gf = (V, E ? Ef) 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|2 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).

Full Text:



  • There are currently no refbacks.