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

VL - 48

SP - 199

EP - 214

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

SN - 0167-5060

IS - C

ER -