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 · 2018
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 = \bigcup_{h = 1}^r V_h$ and Vi∩Vj=∅ (1≤i