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

Shuji TSUKIYAMA  

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

Full Text: PDF(606.1KB)
>>Buy this Article


Summary: 
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.