グラフのk辺連結化問題に対する新しい近似解法

• Item type: SIG Technical Reports(1)
• 公開日: 1994-07-22
• タイトル: グラフのk辺連結化問題に対する新しい近似解法
• タイトル / 言語: en
• タイトル: New Approximation Algorithms for the k -Edge- Connectivity Augmentation Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部第二類回路システム工学講座
• 著者所属: 広島大学工学部第二類回路システム工学講座
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者名: 間島, 利也; 渡辺, 敏正
• 著者名(英): Toshiya, Mashima; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文ではコスト付きのk辺連結化問題（?kE)に対する近似解法について報告する．我我は既にW?kECAに対して4つの近似解法を提案し，比較実験では最大コストマッチングを用いた近似解法FSMが最良であることを示した．ここでは，次の2つの結果を与える．第一に，W?kECAに対する新しい近似解法MWを提案し，辺連結度を1だけ上げるW?kECAに対してMWの近似解は最適解の2倍以下で抑えられることを理論的に証明する．第二に，近似解を改良するための辺の交換手法EXCHANGEを既存の4つの近似解法とMWに組み込み，その有効性を実験的に明示する．さらにEXCHANGEの組み込み後でも，これらの5つの近似解法の中でFSMがやはり最良の近似解を与えることも実験的に示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: New approximation algorithms for the weighted k-edge-connectivity augmentation problem (W-kECA) are considered. We have already proposed four approximation algorithms for W-kECA, and have shown experimentally that the approximation algorithm FSM using maximum-cost matching algorithm gives the best approximation among them. In this paper, two results are given. First, a new approximation algorithm MW is proposed, and it is proved theoretically that MW produces approximation whose total cost can be bounded by twice the optimum for the case where the edge connectivity is increased by one. Secondly a simple postprocessing for improvement of a solution is incorporated into any one of the previous four algorithms as well as MW, and it is experimentally shown that total cost of each solution is greatly reduced. It is also presented that, even after such improvement, FSM remains giving the best approximation among these five algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 69(1994-AL-040), p. 25-32, 発行日 1994-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会