@article{oai:niigata-u.repo.nii.ac.jp:00003308,
 author = {渡辺, 郁 and 田村, 裕 and 仙石, 正和},
 issue = {8},
 journal = {電子情報通信学会論文誌. A, 基礎・境界, 電子情報通信学会論文誌. A, 基礎・境界},
 month = {Aug},
 note = {フローネットワークのロケーション問題として,p-センター問題やp-メジアン問題があり,それらは多項式時間で解けることが知られている.本論文では,フローネットワークの新たな一つのロケーション問題を提案する.それは一つの固定された入口とp個の(固定されていない)出口をもつフローネットワークNを考え,Nに最大フローが最大になるようにp個の出口をうまく配置する問題である(この問題をp-回収問題と呼ぶ).まず木状ネットワークに対する1-回収問題を解く線形時間アルゴリズム,次に動的計画法に基づいた木状ネットワークのp-回収時間を解く疑多項式時間アルゴリズムを与える.また木状ネットワークに対する1-回収問題に対応する判定問題はNP-完全であることが知られているので,その判定問題が強NP-完全でないことがわかる.},
 pages = {938--946},
 title = {フローネットワークの出口配置問題},
 volume = {J78-A},
 year = {1995}
}