グラフのk辺連結化問題に対する新しい近似解法
スポンサーリンク
概要
- 論文の詳細を見る
本論文ではコスト付きのk辺連結化問題(W-kECA)に対する近似解法について報告する.我我は既にW-kECAに対して4つの近似解法を提案し,比較実験では最大コストマッチングを用いた近似解法FSMが最良であることを示した.ここでは,次の2つの結果を与える.第一に,W-kECAに対する新しい近似解法MWを提案し,辺連結度を1だけ上げるW-kECAに対してMWの近似解は最適解の2倍以下で抑えられることを理論的に証明する.第二に,近似解を改良するための辺の交換手法EXCHANGEを既存の4つの近似解法とMWに組み込み,その有効性を実験的に明示する.さらにEXCHANGEの組み込み後でも,これらの5つの近似解法の中でFSMがやはり最良の近似解を与えることも実験的に示す.
- 一般社団法人情報処理学会の論文
- 1994-07-22
著者
関連論文
- 点次数の増加上限制約を持つ2点連結グラフに対する線形時間3点連結化アルゴリズム
- グラフの3-辺連結化について(計算アルゴリズムと計算量の基礎理論)
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点k辺連結化について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- 領域分割に基づく並列配線手法
- アナログ回路用多層プリント基板の分離型設計
- 多層プリント基板設計における回路分割の一手法
- 広島大学工学部第二類(電気系)回路システム工学大講座情報回路網工学研究室
- グラフの辺付加問題による耐故障ネットワ-クの構成
- 耐故障ネットワークと辺付加問題(計算アルゴリズムと計算量の基礎理論)
- マ-クグラフの初等P-インバリアントとP-基底
- 予測・修正混雑コスト方式によるスイッチボックス配線手法 (最適化)
- 固定ルーティングネットワークにおける無故障な経由ルート数の評価
- 辺の付加によるグラフの拡大構成問題(グラフ理論とその応用)
- 辺付加によるグラフの拡大構成問題(計算機科学の基礎理論)
- 3-連結グラフの連結点被覆問題 (形式言語理論とオートマトン理論)
- 辺短絡除去問題のNP-困難性について(技術談話室)
- 辺開放除去問題のNP-困難性について
- 平面グラフの点除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の短絡除去による平面グラフ化問題について
- 辺の短絡除去による平面グラフ化問題--最大節点次数がたかだか3の場合(技術談話室)
- 辺の短絡除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の開放除去による2端子直並列グラフの構成問題(技術談話室)
- ステートマシンの接続構造を持つペトリネットの発火系列問題
- ペトリネットの最小初期部分マーキング問題について(グラフ,ネットワークとアルゴリズムおよび一般)
- 次数制約付きのグラフに対する指定点2点連結化問題の解法
- λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- 複数の求解戦略を持つリアルタイムスケジューリング法
- On Forming a Series-Parallel Graph by Removing Nodes of a Planar Graph (Studies on Computational Complexities and Related Topics)
- 一般ペトリネットにおける極小デッドロック抽出法
- ペトリネットの発火系列問題に対する近似アルゴリズム
- グラフの多重辺付加を許さない4辺連結化問題
- グラフの指定点集合に対するk辺連結化問題
- グラフの多重辺付加を許さない辺連結化問題
- グラフの多重辺付加を許さない4辺連結化問題