The p-collection problem in a flow network with lower bounds

The p-collection problem in a flow network with lower bounds

0.00 Avg rating0 Votes
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: , , ,
Keywords: programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.