13. – 18. Februar 2011, Dagstuhl-Seminar 11071

Theory and Applications of Graph Searching Problems (GRASTA 2011)


Fedor V. Fomin (University of Bergen, NO)
Pierre Fraigniaud (University of Paris VII, FR)
Stephan Kreutzer (TU Berlin, DE)
Dimitrios M. Thilikos (University of Athens, GR)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 1, Issue 2 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


Graph searching is often referred to, in a more playful language, as a pursuit-evasion game (or, alternatively, cops and robbers game). This is a kind of game where one part is a set of escaping mobile entities, called evaders (or fugitives), that hide in a graph representing a network, and the other part is a number of chasing agents, called searchers (or pursuers), that move systematically in the graph. The game may vary significantly according to the capabilities of the evaders and the pursuers in terms of relative speed, sensor capabilities, visibility, etc. The objective of the game is to capture the evaders in an optimal way, where the notion of optimality itself admits several interpretations.

Graph searching revealed the need to express in a formal mathematical way intuitive concepts such as avoidance, surrounding, sense of direction, hiding, persecution, and threatening. There are many variants of graph searching studied in the literature, which are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues in Computer Science, Discrete Mathematics, and Artificial Intelligence including

  • Information Seeking
  • Robot motion planning
  • Graph Theory
  • Database Theory and Robber and Marshals Games
  • Logic
  • Distributed Computing
  • Models of computation
  • Network security

The objective of the seminar was to bring researchers from the widest possible variety of disciplines related to graph searching and we will especially encourage the maximum interplay between theory and applications. The meeting initiated the exchange of research results, ideas, open problems and discussion about future avenues in Graph Searching. As a fruit of this encounter new research results, open problems, and methodologies will appeared, especially those of interdisciplinary character.

Related Dagstuhl-Seminar


  • AI/ Robotics
  • Data Bases/ Information Retrieval
  • Data Structures/ Algorithms/ Complexity
  • Hardware
  • Modelling/simulation
  • Networks
  • Optimization/ Scheduling
  • Security/cryptography
  • Verification/logic
  • WWW/internet
  • Interdisciplinary


  • Graph Searching
  • Pursuit Evasion Games
  • Cop and Robber Games


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.