@article{oai:niigata-u.repo.nii.ac.jp:00001910,
 author = {Watanabe, Kaoru and Tamura, Hiroshi and Sengoku, Masakazu},
 issue = {9},
 journal = {IEICE transactions on fundamentals of electronics, communications and computer sciences, IEICE transactions on fundamentals of electronics, communications and computer sciences},
 month = {Sep},
 note = {The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree ≧ 3 in a network, is bound to some constant K ≧ 0.},
 pages = {1495--1503},
 title = {The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach},
 volume = {E79-A},
 year = {1996}
}