Covering Problems in the p-Collection Problems

Kaoru WATANABE  Masakazu SENGOKU  Hiroshi TAMURA  Shoji SHINODA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A    No.3    pp.470-475
Publication Date: 1998/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 10th Karuizawa Workshop on Circuits and Systems)
location problem,  network flows,  NP-complete,  optimization problem,  

Full Text: PDF>>
Buy this Article

The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.