グラフに対する最大供給分割問題解法の性能評価

スポンサーリンク

概要

論文の詳細を見る
需要点集合V_dと供給点集合V_sの和集合である点集合,および無向辺集合Eを持つグラフG=(V_d∪V_s,E),さらに各需要点υ,の需要量d(υ)>0,各供給点uの供給量s(u)>0が与えられたとする.各供給点u_κ(1[<!_]k[<!_]|V_s|)に対して,Σ_<υ∈Vdκ>d(υ)[<!_]s(u_κ)かつV_<dκ> ∪{u_κ}のGでの誘導部分グラフが連結であるような,互いに素な需要点集合V_<dκ>の族{V_<dκ>|1[<!_]k[<!_]|V_s|}を求める.これらの需要点集合に属する需要点の需要量総和が最大となるような需要点集合族を求める問題を"グラフの最大供給分割問題"と呼ぶ.本橋では,グラフの最大供給分割問題に対する既存の発見的解法と最適解法に着目し,提案する改良手法と共に計算機上で実装して,これらの性能を計算機実験により比較評価する.
一般社団法人情報処理学会の論文
2003-09-19

著者

関連論文

もっと見る

スポンサーリンク