- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on June 30, 2025】Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
フローネットワークの出口配置問題
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
-
- 電子情報通信学会論文誌. A, 基礎・境界
-
電子情報通信学会論文誌. A, 基礎・境界 J78-A (8), 938-946, 1995-08
電子情報通信学会
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050564289190595840
-
- NII Article ID
- 110003312249
-
- NII Book ID
- AN10013345
-
- ISSN
- 09135707
-
- HANDLE
- 10191/18484
-
- NDL BIB ID
- 3621755
-
- Text Lang
- ja
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- NDL Search
- CiNii Articles