Best location of service centers in a treelike network under budget constraints

DOI10.1016/0012-365X(90)90361-KMaRDI QIDQ2639769zbMATH OpenOpenAlexFDO

Authors James A. M. McHugh, Yehoshua Perl

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90361-k

zbMATH Keywords

maximum weight k-domination problemNP-hardpseudopolynomial methodstree network

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Programming involving graphs or networks (90C35) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Review text

Consider a tree network with a weight (population) and a cost (to set up a service center) associated with each vertex. Any center will service both the vertex at which it lies and its adjacent vertices. The aim is to locate service centers so that total setup cost remains within a given budget, and maximising the total population served. This problem is shown to be NP-hard in general. For the case where all setup costs are equal a polynomial dynamic programming algorithm is derived. For the general case two pseudopolynomial methods are given, one by way of traditional dynamic programming, the second, more efficient one, by way of a modified left-right dynamic programming method.

Recommendations

• scientific article; zbMATH DE number 3843458
• scientific article; zbMATH DE number 961964
• The multi-service center problem
• Locating A Median Subtree On A Network
• scientific article; zbMATH DE number 4051314

Cites work

• A linear algorithm for the domination number of a tree
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Circuit partitioning with size and connection constraints
• Efficient Algorithm for the Partitioning of Trees
• Efficient Optimization of Monotonic Functions on Trees
• scientific article; zbMATH DE number 3918387 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Optimum domination in weighted trees

Cited in

(7)

• Optimal M/G/1 server location on a tree network with continuous link demands
• scientific article; zbMATH DE number 3843458 (Why is no real title available?)
• scientific article; zbMATH DE number 4051314 (Why is no real title available?)
• Dynamic location problems with radial structure of the components of the connecting graph
• scientific article; zbMATH DE number 710577 (Why is no real title available?)
• Controlling and optimizing the transport (search) efficiency with local information on a class of scale-free trees
• Bibliography on domination in graphs and some basic definitions of domination parameters

This page was built for publication: Best location of service centers in a treelike network under budget constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639769)