A Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints

• Item type: SIG Technical Reports(1)
• 公開日: 2010-09-15
• タイトル: A Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints
• タイトル / 言語: en
• タイトル: A Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Engineering, Hiroshima University
• 著者所属: Graduate School of Engineering, Hiroshima University
• 著者所属: Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者名: Tadachika, Oki; Satoshi, Taoka; Toshimasa, Watanabe
• 著者名(英): Tadachika, Oki; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-131, 号 10, p. 1-8, 発行日 2010-09-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会