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


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A       pp.139-146
Publication Date: 1998/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Category: Graphs and Networks
flow network,  location problem,  p-collection problem,  dynamic programming,  

Full Text: PDF>>
Buy this Article

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.