IEICE TRANSACTIONS on Fundamentals
A New Algorithm forp-Collection Problem on a Tree-Type Flow Network
Summary :
For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.1 pp.139-146
- Publication Date
- 1998/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- 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
Shuji TSUKIYAMA, "A New Algorithm forp-Collection Problem on a Tree-Type Flow Network" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 1, pp. 139-146, January 1998, doi: .
Abstract: For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_1_139/_p
Copy
@ARTICLE{e81-a_1_139,
author={Shuji TSUKIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Algorithm forp-Collection Problem on a Tree-Type Flow Network},
year={1998},
volume={E81-A},
number={1},
pages={139-146},
abstract={For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A New Algorithm forp-Collection Problem on a Tree-Type Flow Network
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 139
EP - 146
AU - Shuji TSUKIYAMA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1998
AB - For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc
ER -
English
