Strategic Deployment in Graphs
Abstract
Conquerors of old (like, e.g., Alexander the Great or Ceasar) had to solve the following deployment problem.
Sufficiently strong units had to be stationed at locations of strategic importance, and the moving
forces had to be strong enough to advance to the next location. To the best of our knowledge we are the
first to consider the (off-line) graph version of this problem. While being NP-hard for general graphs, for
trees the minimum number of agents and an optimal deployment can be computed in optimal polynomial
time. Moreover, the optimal solution for the minimum spanning tree of an arbitrary graph G results in a
2-approximation of the optimal solution for G.
Sufficiently strong units had to be stationed at locations of strategic importance, and the moving
forces had to be strong enough to advance to the next location. To the best of our knowledge we are the
first to consider the (off-line) graph version of this problem. While being NP-hard for general graphs, for
trees the minimum number of agents and an optimal deployment can be computed in optimal polynomial
time. Moreover, the optimal solution for the minimum spanning tree of an arbitrary graph G results in a
2-approximation of the optimal solution for G.
Full Text:
PDF
This work is licensed under a Creative Commons Attribution 3.0 License.