Problems of Where to Locate p-Sinks in a Flow Network.

As location problems in flow networks, there are p-center and p-median problems; and they are known to be solvable in polynomial time. In this paper, wer propse a new location problem. It is the problem of locating p-sinks so that the maximum flow is maximized given a flow network N with a source (this problem is called a p-collection problem). First, a linear time algorithm to solve the 1-collection problem for trees in given. Then a pseudo-polynomial time algorithm to solve the p-collection problem for trees based on dynamic programming is presented. Since the decision problem corresponding to the p-collection problem for trees is known to be NP-complete, its decision problem turns out to be strongly NP-complete. [ABSTRACT FROM AUTHOR]