書誌事項
- タイトル別名
-
- フロー ネットワーク ノ デグチ ハイチ モンダイ
- Problems of Where to Locate p-Sinks in a Flow Network
この論文をさがす
説明
フローネットワークのロケーション問題として,p-センター問題やp-メジアン問題があり,それらは多項式時間で解けることが知られている.本論文では,フローネットワークの新たな一つのロケーション問題を提案する.それは一つの固定された入口とp個の(固定されていない)出口をもつフローネットワークNを考え,Nに最大フローが最大になるようにp個の出口をうまく配置する問題である(この問題をp-回収問題と呼ぶ).まず木状ネットワークに対する1-回収問題を解く線形時間アルゴリズム,次に動的計画法に基づいた木状ネットワークのp-回収時間を解く疑多項式時間アルゴリズムを与える.また木状ネットワークに対する1-回収問題に対応する判定問題はNP-完全であることが知られているので,その判定問題が強NP-完全でないことがわかる.
収録刊行物
-
- 電子情報通信学会論文誌. A, 基礎・境界
-
電子情報通信学会論文誌. A, 基礎・境界 J78-A (8), 938-946, 1995-08
電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1050564289190595840
-
- NII論文ID
- 110003312249
-
- NII書誌ID
- AN10013345
-
- ISSN
- 09135707
-
- HANDLE
- 10191/18484
-
- NDL書誌ID
- 3621755
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- IRDB
- NDL
- CiNii Articles