連結グラフの局所2点連結化増大問題に対する4/3-近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
連結グラフG=(V,E)および節点対の集合Rが与えられたとき,Gに最小本数の新しい辺の集合Fを加え,増大されたグラフG+Fにおいてどの節点対(u,v)∈Rの間にも2本の内素なパスが取れるようにしたい.この問題はNP-困難であることが示されており,これまでに3/2-近似アルゴリズムが知られている.本論文では,この近似アルゴリズムで使われている最適値に対する下界を改良することにより,O(|E|+|R|)時間で4/3-近似の解を求めるアルゴリズムを設計する.
- 2002-04-18
論文 | ランダム
- 数式処理システムによる非線形計画問題の3次元グラフィックス表現について(数式処理における理論と応用の研究)
- 半導体ビジネスの収益構造と採算管理システム : DRAMなどの半導体汎用製品を中心として
- ファジィ数を含む多目的非凸計画問題に対する浮動小数点型遺伝的アルゴリズムによる対話型ファジィ満足化手法
- ある種の非線形計画問題の代数的解放について
- 最適設計のための非線形計画法ライブラリの開発 その2 内接超球法