2024-03-29T11:41:52Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00001910
2022-12-15T03:34:45Z
423:424:425
453:454
The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
Watanabe, Kaoru
Tamura, Hiroshi
Sengoku, Masakazu
copyright©1996 IEICE
location problem
flow network
NP-complete
optimization problem
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.
The Institute of Electronics, Information and Communication Engineers
1996-09
eng
journal article
http://hdl.handle.net/10191/6521
https://niigata-u.repo.nii.ac.jp/records/1910
http://www.ieice.org/jpn/trans_online/
AA10826239
09168508
IEICE transactions on fundamentals of electronics, communications and computer sciences
IEICE transactions on fundamentals of electronics, communications and computer sciences
E79-A
9
1495
1503
https://niigata-u.repo.nii.ac.jp/record/1910/files/e79-a_9_1495.pdf
application/pdf
758.1 kB
2019-07-29