HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Graph Searching and Graph Decompositions

Nicolas Nisse 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Graph searching is a game where a team of mobile agents must catch a fugitive hidden in a network (modelled by a graph). Equivalently, graph searching may be defined in terms of clearing a contaminated network. Besides of its practical interests, graph searching has been widely studied for its relationship with important graph parameters, in particular pathwidth and treewidth. Many versions of graph searching problems have been considered. They all look for a strategy that allows to catch the fugitive using the minimum number of agents. Variants of graph searching differ on various parameters. We first give a brief survey of the numerous research directions in this field. Then, we focus on the relationship between search games and graph decompositions (path- and tree-decompositions). Namely, search games provide a very interesting algorithmic interpretation of the pathwidth and the treewidth of graphs. we explain the equivalence between theses games and graph decompositions through an important property of these two search games: the monotonicity. This point of view allowed us to obtain new duality results generalyzing those obtained by Robertson and Seymour in the Graph Minors Theory.
Complete list of metadata

Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Sunday, May 9, 2010 - 12:23:12 AM
Last modification on : Friday, February 4, 2022 - 3:15:44 AM


  • HAL Id : inria-00482115, version 1



Nicolas Nisse. Graph Searching and Graph Decompositions. 24th European Conference on Operational Research (EURO) (2010), Jul 2010, Lisbon, Portugal. ⟨inria-00482115⟩



Record views