重み付き次数制約を持つネットワーク設計問題

概要

論文の詳細を見る
重みw:E×V→Q_+が与えられている無向グラフG=(V,E)を考える.節点v∈Vの重み付き次数d_w(v;E)をΣ{w(e,v)|vに接続する辺e∈E}と定義する.本研究では,各節点の重み付き次数に対する上限が制約として与えられているネットワーク設計問題を考える.問題の入力は,辺集合E=E_1∪^^・E_2∪^^・E_3を持つ無向グラフG=(V,E),辺コストc:E→Q,次数上限b:V→Q_+である.解は全域木T⊆Eと重みw_i:T_i×V→Q+(i∈{2,3})から成る(ただし,T_i=T∩E_i).w_2(e,u)+w_2(e,v)=μ(e)(e=uv∈T_2),{w_3(e,u),w_3(e,v)}={0,ν(e)}(e=uv∈T_3),d_<w1>(v;T_1)+d_<w2>(v;T_2)+d_<w3>(v;T_3)≤(v)(v∈V)を満たすとき,解が実行可能であると定義する.問題の目的は,Σ_<e∈T>c(e)が最小となる実効可能解を求めることである.我々は,重み付き次数に関する制約を違反することを許した上で,コストと重み付き次数を同時に抑えるような解を計算するアルゴリズムを提案する.また,解の最大重み付き次数を最小化する問題についても考える.
2008-05-20