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

機関リポジトリ 機関リポジトリ HANDLE Web Site 被引用文献2件 参考文献7件

書誌事項

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

この論文をさがす

説明

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

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (7)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ