著者

Tadachika OKI Satoshi TAOKA Toshiya MASHIMA Toshimasa WATANABE

出版者

一般社団法人 電子情報通信学会

雑誌

IEICE Transactions on Information and Systems (ISSN:09168532)

巻号頁・発行日

vol.E95.D, no.3, pp.769-777, 2012-03-01 (Released:2012-03-01)

参考文献数

15

被引用文献数

1

---

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}.

著者

Tadachika OKI Satoshi TAOKA Toshiya MASHIMA Toshimasa WATANABE

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Information and Systems (ISSN:09168532)

巻号頁・発行日

vol.E95-D, no.3, pp.769-777, 2012-03-01

被引用文献数

1

---

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}.

著者

Tadachika Oki Satoshi Taoka Toshimasa Watanabe

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-131, no.10, pp.1-8, 2010-09-15

---

The k-edge-connectivity augmentation problem with multipartition constraints (kECAM for short) is defined by “Given an undirected graph G = (V, E) and a multipartition π = {V1, . . . , Vr} of V with Vi ∩ Vj = ∅ for ∀i, j ∈ {1, . . . , r} (i ≠ j), find an edge set E' of minimum cardinality, consisting of edges that connect distinct members of π, such that G' = (V, E ∪ E') is k-edge-connected.”In this paper, we propose a fast algorithm for finding a solution to (σ+1)ECAM when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}. The main idea is to reduce (σ + 1)ECAM to the bipartition case, that is, (σ+1)ECAM with r = 2. Moreover, we propose a parallel algorithm for finding a solution to (σ + 1)ECAM, when a structural graph F(G) which represents all minimum cuts of G is given and σ is odd.

著者

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.