次数制約付き点連結度ネットワーク設計問題に対する反復丸め近似アルゴリズム(特別企画)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,辺コストを持っグラフと次数の上限b(・)が与えられたときに,指定された連結度要求を満たし,かつ各点νの次数が高々わb(ν)であるような最小コスト部分グラフを求める問題について議論する.本論文ではこの問題に対して反復丸め法に基づく近似アルゴリズムを与える.グラフが無向グラフであり,連結度要求が要素連結度に関するもので最大値んである場合,提案アルゴリズムは近似比O(κ)の辺コストを持ち点νの次数が0(κ)・b(ν)以下であるような解を計算する.また,辺コストが与えられずに連結度要求と次数制約を満たす部分グラフを見っける問題についても議論し,同様のケースでは点νの次数が6b(ν)+0(κ^2)以下であるような部分グラフをアルゴリズムが計算することを示す.これらのアルゴリズムは要素連結度要求の代わりに点連結度要求を持つ問題に対しても拡張することが可能である.
- 2012-12-03