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

摘要

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by "Given an undirected graph G = (V, E) and a bipartition n = V_b, V_w} of V with V_b ∩ V_w = 0, find an edge set E_f of minimum cardinality, consisting of edges that connect V_b and Vw, such that G' = (V, E ∪ E_f) is k-edge-connected." The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(VE +V~2 log V) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1,2}.