木状ネットワークにおけるp-回収問題に対する新手法

概要

論文の詳細を見る
木状ネットワークにおけるp-回収問題とは, 台グラフが木であるような対称有向グラフD=(V,A)において, 枝容量c(・)と点重みd(・)が与えられたとき, 正の点重みを持つ入口からp個の出ロへのフローの値が最大になるように出口を配置する問題で, フローネットワークにおける資源配置問題の1つである[1]. 枝容量および点重みはいずれも非負整数で, d(V)>0なる入口では, d(V)のフローがDに供給可能であり, 出口では任意の値のフローがDから出て行くことができる. この木状ネットワークにおけるp-回収問題はNP-困難であるが[1], 点の個数をn, 枝容量あるいは点重みの最大値をCとしたとき, 動的計画法を用いたO(p^2n^3C^2)の時間計算量の擬多項式時間アルゴリズムが提案されており, 一般の場合と違い, 強NP-完全でないことが分かっている[2]. 本稿では, [2]の手法より単純で, 時間計算量がO(p^2n^2C^2)の新しい擬多項式時間アルゴリズムを提案する.
社団法人電子情報通信学会の論文
1997-03-06