平面的2辺連結化問題に対する解法の実験的評価

• Item type: SIG Technical Reports(1)
• 公開日: 2001-09-25
• タイトル: 平面的2辺連結化問題に対する解法の実験的評価
• タイトル / 言語: en
• タイトル: Experimental Evaluation of Algorithms for the Planar 2 -Edge- Connectivity Augmentation Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): 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
• 著者名: 今井, 英敏; 高藤, 大介; 田岡, 智志; 渡邉, 敏正
• 著者名(英): Hidetoshi, Imai; Daisuke, Takafuji; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面的2辺連結化問題を次のように定義する：「連結な平面的グラフG=(V E)が与えられたとき，G'=(V E ?cup E')が2辺連結平面的グラフとなる最小本数の付加辺集合E'を見つけよ．」ここで，グラフが2辺連結であるとは，どの１本の辺を取り除いても非連結にならないことである．また，平面的グラフとは辺を交差せずに平面に描くことができるグラフである．本稿では，既存の2-近似解法 2OPT の改良版である2つの2-近似解法B2OPT と SETP ，および発見的解法 ETP を提案し，これら4解法の実験的比較により，提案解法の有用性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The planar 2-connectivity augmentation problem is defined as follows: given a connected planar graph G = (V,E), find an edge set E' of minimum cardinality such that G' = (V,E \cup E') is 2-connected and still planar. In this paper, we propose three algorithms: two 2-approximation algorithms B2OPT and SETP, which are modified versions of the 2-approximation algorithm 2OPT, and a heuristic algorithm ETP. Experimental comparison shows superiority of our proposed algorithms over 2OPT.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 93(2001-AL-080), p. 9-16, 発行日 2001-09-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会