Reduction of Constraints from Multipartition to Bipartition in Augmenting Edge-Connectivity of a Graph by One

Satoshi TAOKA  Tadachika OKI  Toshiya MASHIMA  Toshimasa WATANABE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.2   pp.357-366
Publication Date: 2018/02/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
connectivity augmentation problems,  edge-connectivity,  multipartition constraints,  graphs,  polynomial time algorithms,  

Full Text: PDF(770.3KB)
>>Buy this Article

The k-edge-connectivity augmentation problem with multipartition constraints (kECAMP, for short) is defined by “Given a multigraph G=(V,E) and a multipartition π={V1,...,Vr} (r≥2) of V, that is, $V = igcup_{h = 1}^r V_h$ and Vi∩Vj=∅ (1≤i<jr), find an edge set Ef of minimum cardinality, consisting of edges that connect Vi and Vj (ij), such that (V,EEf) is k-edge-connected, where a multigraph means a graph, with unweighted edges, such that multiple edges may exist.” The problem has applications for constructing a fault-tolerant network under building constraints, and so on. In this paper, we give a linear time reduction of (σ+1)ECAMP with |π| ≥ 3 to (σ+1)ECAMP with |π|=2 when the edge-connectivity of G is σ and a structural graph F(G) of G is given.