Article ID: | iaor1999856 |
Country: | Japan |
Volume: | E80A |
Issue: | 4 |
Start Page Number: | 651 |
End Page Number: | 657 |
Publication Date: | Apr 1997 |
Journal: | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |
Authors: | Watanabe K., Tamura H., Nakano K., Sengoku M. |
Keywords: | programming: dynamic |
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.