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

Tadachika OKI  Satoshi TAOKA  Toshiya MASHIMA  Toshimasa WATANABE 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E95-D  No.3  pp.769-777
Publication Date: 2012/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
connectivity augmentation problems,  edge-connectivity,  bipartition constraints,  graphs,  polynomial time algorithms, 

Full Text: PDF(341.7KB)

Summary: 
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 π = {VB, VW} of V with VB ∩ VW = ∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V, E ∪ Ef) 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(|V||E| + |V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.