Graph Searching (12w5055)


(University of Bergen)

(Dalhousie University)

(Ryerson University)

(LIRMM, Univ Montpellier, CNRS)


The Banff International Research Station will host the "Graph Searching" workshop from October 7th to October 12th, 2012.

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 agents, 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 depending on the underlying model, which could be taken from, to name just three, areas of: Robot Motion Planning; Network Security; Decontamination of and the prevention of the spread of viruses in a computer or real life network.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).