フロｰネットワｰクのロケｰション問題の一考察

4 References

Bibliographic Information

Other Title
  • A Study on a location Problem in Flow Network

Search this article

Description

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.

Journal

References(4)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1571980077284032512
  • NII Article ID
    110003198193
  • NII Book ID
    AN10013094
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top