Graph Searching and Graph Decompositions

Nicolas Nisse 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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.
Type de document :
Communication dans un congrès
24th European Conference on Operational Research (EURO) (2010), Jul 2010, Lisbon, Portugal. 2010
Liste complète des métadonnées
Contributeur : Nicolas Nisse <>
Soumis le : dimanche 9 mai 2010 - 00:23:12
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04


  • 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. 2010. 〈inria-00482115〉



Consultations de la notice