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

作者：Oki Tadachika^*; Taoka Satoshi; Mashima Toshiya; Watanabe Toshimasa

来源：IEICE Transactions on Information and Systems, 2012, E95D(3): 769-777.

DOI：10.1587/transinf.E95.D.769

• connectivity augmentation problems
• edge-connectivity
• bipartition constraints
• graphs
• polynomial time algorithms

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by %26quot;Given an undirected graph G = (V, E) and a bipartition pi = {V-B, V-W} of V with V-B boolean AND V-W = theta, find an edge set E-f of minimum cardinality, consisting of edges that connect V-B and V-w, such that G%26apos; = (V, E boolean OR E-f) is k-edge-connected.%26quot; 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 (sigma + 1)ECABP in O(vertical bar V vertical bar vertical bar E vertical bar + vertical bar V-2 vertical bar log vertical bar V vertical bar) time when G is sigma-edge-connected (sigma %26gt; 0), and show that the problem can be solved in linear time if sigma is an element of {1, 2}.

• 出版日期2012-3