TY - JOUR
T1 - Best Location of Service Centers in a Treelike Network Under Budget Constraints
AU - Mchugh, James
AU - Perl, Yehoshua
N1 - Funding Information:
Supported in part by the State of New Jersey SBR Grants
PY - 1991/1/1
Y1 - 1991/1/1
N2 - We consider the problem of locating service centers in a treelike network in order to maximize the serviced population under budget constraints. We show that the problem is NP-hard. In the case where the costs of establishing the service centers are equal for all n cities we obtain the maximum weight fc-domination problem. An 0(nk2) dynamic programming procedure is given. Then an 0(nB2) pseudo-polynomial dynamic programming procedure is presented for the original problem, where B is the budget constraint. Finally a variation of the new left-right dynamic programming technique is applied to obtain a more efficient pseudo-polynomial procedure.
AB - We consider the problem of locating service centers in a treelike network in order to maximize the serviced population under budget constraints. We show that the problem is NP-hard. In the case where the costs of establishing the service centers are equal for all n cities we obtain the maximum weight fc-domination problem. An 0(nk2) dynamic programming procedure is given. Then an 0(nB2) pseudo-polynomial dynamic programming procedure is presented for the original problem, where B is the budget constraint. Finally a variation of the new left-right dynamic programming technique is applied to obtain a more efficient pseudo-polynomial procedure.
UR - http://www.scopus.com/inward/record.url?scp=77957072809&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957072809&partnerID=8YFLogxK
U2 - 10.1016/S0167-5060(08)71050-1
DO - 10.1016/S0167-5060(08)71050-1
M3 - Article
AN - SCOPUS:77957072809
SN - 0167-5060
VL - 48
SP - 199
EP - 214
JO - Annals of Discrete Mathematics
JF - Annals of Discrete Mathematics
IS - C
ER -