MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEDistributed graph searching
par Nicolas Nisse
| Date : | 09/10/08 | | Location : | Coriolis |
Graph searching is a game in which a team of searchers is aiming at capturing an invisible fugitive running in a graph, or, equivalently, at clearing a contaminated network. In a centralized setting, the goal consists in computing a search strategy allowing the minimum number of searchers to clear the network. In distributed graph searching, the searchers are modeled by automata with logarithmic size memory. They must compute their own search strategy for clearing the network in which they are currently running. This distributed computation must not require knowing the topology of the network in advance, and the searchers must act in absence of any global synchronization mechanism. In this talk, we present a short literature survey that answers the following general questions. Is it possible to design a distributed algorithm that allows to clear any graph with the optimal (in centralized settings) number of searchers? What happens if the distributed strategy is constrained to be monotone? Can we help the searchers by giving them some information about the graph (size, topology…)?
Page des séminaires
| 
