For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1998/03/25
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(526.4KB)>>
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.