1-1hit |
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.