IEICE TRANSACTIONS on Fundamentals
The p-Collection Problem in a Flow Network with Lower Bounds
Summary :
In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.4 pp.651-657
- Publication Date
- 1997/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
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, Keisuke NAKANO, Masakazu SENGOKU, "The p-Collection Problem in a Flow Network with Lower Bounds" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 4, pp. 651-657, April 1997, doi: .
Abstract: In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_4_651/_p
Copy
@ARTICLE{e80-a_4_651,
author={Kaoru WATANABE, Hiroshi TAMURA, Keisuke NAKANO, Masakazu SENGOKU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The p-Collection Problem in a Flow Network with Lower Bounds},
year={1997},
volume={E80-A},
number={4},
pages={651-657},
abstract={In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - The p-Collection Problem in a Flow Network with Lower Bounds
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 651
EP - 657
AU - Kaoru WATANABE
AU - Hiroshi TAMURA
AU - Keisuke NAKANO
AU - Masakazu SENGOKU
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1997
AB - In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.
ER -
English
