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 “Given a multigraph G = (V,E) and a bipartition π = {VB,VW} of V with VBVW = ∅, find an edge set E of minimum size, consisting of edges that connect VB and VW, such that Gf = (V, EEf) 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.