COVERING PROBLEMS IN THE P-COLLECTION PROBLEMS

Authors
WATANABE K SENGOKU M TAMURA H SHINODA S
Citation
K. Watanabe et al., COVERING PROBLEMS IN THE P-COLLECTION PROBLEMS, IEICE transactions on fundamentals of electronics, communications and computer science, E81A(3), 1998, pp. 470-475
Citations number
9
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E81A
Issue
3
Year of publication
1998
Pages
470 - 475
Database
ISI
SICI code
0916-8508(1998)E81A:3<470:CPITPP>2.0.ZU;2-J
Abstract
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 m aximum flow is maximum. This paper discusses the cover problems corres ponding to the lower bounded p-collection problem. We consider the com plexity of the cover problem, and we show polynomial time algorithms f or its subproblems in a network with tree structure.