フローネットワークの出口配置問題

IR IR IR IR (HANDLE) Web Site 2 Citations 7 References

Bibliographic Information

Other Title
  • フロー ネットワーク ノ デグチ ハイチ モンダイ
  • Problems of Where to Locate p-Sinks in a Flow Network

Search this article

Description

フローネットワークのロケーション問題として,p-センター問題やp-メジアン問題があり,それらは多項式時間で解けることが知られている.本論文では,フローネットワークの新たな一つのロケーション問題を提案する.それは一つの固定された入口とp個の(固定されていない)出口をもつフローネットワークNを考え,Nに最大フローが最大になるようにp個の出口をうまく配置する問題である(この問題をp-回収問題と呼ぶ).まず木状ネットワークに対する1-回収問題を解く線形時間アルゴリズム,次に動的計画法に基づいた木状ネットワークのp-回収時間を解く疑多項式時間アルゴリズムを与える.また木状ネットワークに対する1-回収問題に対応する判定問題はNP-完全であることが知られているので,その判定問題が強NP-完全でないことがわかる.

Journal

Citations (2)*help

See more

References(7)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top