13.02.11  18.02.11Dagstuhl Seminar 11071Theory and Applications of Graph Searching ProblemsSeminar Materials (please download your abstracts and talks here) OrganizationFedor V. Fomin (University of Bergen) Pierre Fraigniaud (CNRS and University Paris Diderot) Stephan Kreutzer (University of Oxford) Dimitrios M. Thilikos (National and Kapodistrian University of Athens) MotivationGraph searching is often referred to, in a more playful language, as a pursuitevasion 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
Our intention is 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. This meeting will initiate the exchange of research results, ideas, open problems and discussion about future avenues in Graph Searching. As a fruit of this encounter, we expect that new research results, open problems, and methodologies will appear, especially those of interdisciplinary character. Classification
Keywords
