Covering Problems n the p-Collection Problems

摘要

The lower-bonded p-collection problem is the problem where tolocate p sinks in a flow network with lower bounds such that thevalue of a maximum flow is maximum. This paper discusses the coverproblems corresponding to the lower bounded p-collection problem. Weconsider the complexity of the cover problem, and we show polynomialtime algorithms for its subproblems in a network with tree structure.