Best Location of Service Centers in a Treelike Network Under Budget Constraints

James Mchugh, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)199-214
Number of pages16
JournalAnnals of Discrete Mathematics
Issue numberC
StatePublished - Jan 1 1991

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Best Location of Service Centers in a Treelike Network Under Budget Constraints'. Together they form a unique fingerprint.

Cite this