IEICE TRANSACTIONS on Fundamentals
The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
Summary :
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
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.9 pp.1495-1503
- Publication Date
- 1996/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kaoru WATANABE, Hiroshi TAMURA, Masakazu SENGOKU, "The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach" in IEICE TRANSACTIONS on Fundamentals,
vol. E79-A, no. 9, pp. 1495-1503, September 1996, doi: .
Abstract: 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
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_9_1495/_p
Copy
@ARTICLE{e79-a_9_1495,
author={Kaoru WATANABE, Hiroshi TAMURA, Masakazu SENGOKU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach},
year={1996},
volume={E79-A},
number={9},
pages={1495-1503},
abstract={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
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1495
EP - 1503
AU - Kaoru WATANABE
AU - Hiroshi TAMURA
AU - Masakazu SENGOKU
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1996
AB - 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
ER -
English
