Covering Problems in the p-Collection Problems

Kaoru WATANABE  Masakazu SENGOKU  Hiroshi TAMURA  Shoji SHINODA  

Publication
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: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 10th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
location problem,  network flows,  NP-complete,  optimization problem,  

Full Text: PDF(526.4KB)>>
Buy this Article




Summary: 
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.