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

DOI10.1016/0012-365X(90)90361-KzbMath0718.90053OpenAlexW2075371755MaRDI QIDQ2639769

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

NP-hardtree networkmaximum weight k-domination problempseudopolynomial methods

Mathematics Subject Classification ID

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

Related Items (1)

Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• A linear algorithm for the domination number of a tree
• Optimum domination in weighted trees
• Efficient Optimization of Monotonic Functions on Trees
• Circuit partitioning with size and connection constraints
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Efficient Algorithm for the Partitioning of Trees
• Unnamed Item
• Unnamed Item

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