Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Strategic deployment in graphs
 Informatica 39 (2015), Nr.3, S.237247 ISSN: 03505596 

 Englisch 
 Zeitschriftenaufsatz 
 Fraunhofer FKIE () 
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 (offline) graph version of this problem. While being NPhard 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 2Approximation of the optimal solution for G.