フロｰネットワｰクのロケｰション問題の一考察
書誌事項
- タイトル別名
-
- A Study on a location Problem in Flow Network
この論文をさがす
説明
p-回収問題と呼ばれるフローネットワーク上のロケーション問題をフロー下限を持つフローネットワークに拡張する. 実際上重要な部分問題の計算量について議論し, 各出口の容量が3以上の定数で押さえられているようなネットワークに対して, その問題がNP-完全であることを証明する. また動的計画法を用いた木状ネットワークに対する疑多項式時間アルゴリズムを与え, また連結なネットワークに対するアルゴリズムを提案する. このアルゴリズムは指数時間アルゴリズムではあるが, 入口の重みの絶対値, 弧の容量の絶対値, 補木の弧の数がそれぞれ, ある定数で押さえらた場合は多項式時間で走る.
In this report we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the general p-collection problem. First we discuss subproblems of the general p-collection problem to obtain strongly NP-complete results of restricted subproblems such that the capacity of each sink in a network is bound to some constant equal or grater than three. Next we present a pseud-polynomial time algorithm for this problem in a tree network, and we present an algorithm for this problem in connected networks. Although this algorithm is an exponential algorithm, it runs in polynomial time when the absolute value of the capacity of each arc, the absolute value of the weight of each vertex, and the number of arcs of a cotree in the network are respectively less than fixed constants.
収録刊行物
-
- 電子情報通信学会技術研究報告. CAS, 回路とシステム
-
電子情報通信学会技術研究報告. CAS, 回路とシステム 95 (483), 17-22, 1996-01-26
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1571980077284032512
-
- NII論文ID
- 110003198193
-
- NII書誌ID
- AN10013094
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles