2022-05-25T14:59:21Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000702752020-04-01T00:33:29Z01164:02592:05970:06157
A Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition ConstraintsA Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraintsenghttp://id.nii.ac.jp/1001/00070275/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=70275&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of JapanGraduate School of Engineering, Hiroshima UniversityGraduate School of Engineering, Hiroshima UniversityGraduate School of Engineering, Hiroshima UniversityTadachika, OkiSatoshi, TaokaToshimasa, WatanabeThe 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.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.AN1009593X研究報告アルゴリズム（AL）2010-AL-13110182010-09-152010-09-03