著者

Satoshi TAOKA Tadachika OKI Toshiya MASHIMA Toshimasa WATANABE

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E101-A, no.2, pp.357-366, 2018-02-01

---

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<j≤r), find an edge set Ef of minimum cardinality, consisting of edges that connect Vi and Vj (i≠j), such that (V,E∪Ef) 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.