
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Problem of where to Locate pSinks in a Flow Network: Complexity Approach
Kaoru WATANABE Hiroshi TAMURA Masakazu SENGOKU
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E79A
No.9
pp.14951503 Publication Date: 1996/09/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: location problem, flow network, NPcomplete, optimization problem,
Full Text: PDF>>
Summary:
The pcollection 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 pcollection problem. We prove that the decision problem corresponding to the pcollection problem is strongly NPcomplete. Although location problems (the pcenter problem and the pmedian problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the pcollection problem in networks with tree structure, is weakly NPcomplete. And we show a polynomial time algorithm for the subproblem of the pcollection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.

