The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] p-collection problem(1hit)

1-1hit
  • A New Algorithm forp-Collection Problem on a Tree-Type Flow Network

    Shuji TSUKIYAMA  

     
    PAPER-Graphs and Networks

      Vol:
    E81-A No:1
      Page(s):
    139-146

    For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc min {Cc,Cd}), whereCc andCd are the maximum edge capacity and the maximum vertex weight, respectively.