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.
Vol. 39, No.3

Authors

  • Elmar Langetepe
  • Andreas Lenerz
  • Bernd Brüggemann

Downloads

How to Cite

Langetepe, E. . ., Lenerz, A. ., & Brüggemann, B. . (2015). Strategic Deployment in Graphs. Informatica, 39(3). Retrieved from https://www.informatica.si/index.php/informatica/article/view/979

Issue

Vol. 39 No. 3 (2015)

Section

Special issue papers

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.