Scope of the Event
Graph Searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at capturing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit-evasion game or cops and robbers game. In particular, the graph searching games may vary significantly according to the capabilities of the evaders and the pursuers in terms of relative speed, sensor capabilities, visibility, etc. Also, the notion of capture itself admits several interpretations.
These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues at the intersection of Computer Science, Discrete Mathematics, and Artificial Inteligence. In what follows, we mention some areas in which Graph Searching has significant (practical and fundamental) applications.
- Information Seeking,
- Robot Motion Planning,
- Graph Theory,
- Database Theory and Cops and Marshals Games,
- Game Theory,
- Bounded-resource Reasoning in AI,
- Distributed Computing,
- VLSI Design,
- Models of Computation,
- Routing in Telecommunication Networks,
- Network Security.
The aim of this workshop is to bring together researchers working in these areas in order to exchange problems, ideas, techniques, and results. The objective is to create a clearer picture of the state of the art in the field, to identify outstanding open problems and research directions, and to foster collaborative investigation of selected problems.
- Steve Alpern (Warwick Business School, University of Warwick, United Kingdom)
- Spyros Angelopoulos (CNRS and Sorbonne Université, France)
- Fedor Fomin (University of Bergen, Norway)
- Pierre Fraigniaud (CNRS and University Paris Diderot, France)
- Archontia Giannopoulou (Technische Universität Berlin, Germany)
- Nicolas Nisse (Inria, Université Nice Sophia Antipolis, CNRS, I3S, UMR 7271, Sophia Antipolis, France)
- Richard Nowakowski (Dept. of Mathematics & Statistics, Dalhousie University, Canada)
- Roman Rabinovich (Technische Universität Berlin, Germany)
- Sebastian Siebertz (University of Warsaw, Poland)
- Dimitrios Thilikos (AlGCo project-team, CNRS, LIRMM, France)