Pursuit-evasion, decompositions and convexity on graphs

Ronan Pardo Soares 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.
Document type :
Liste complète des métadonnées

Cited literature [72 references]  Display  Hide  Download

Contributor : Abes Star <>
Submitted on : Thursday, February 6, 2014 - 10:16:15 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Tuesday, May 6, 2014 - 10:30:13 PM


Version validated by the jury (STAR)


  • HAL Id : tel-00908227, version 2



Ronan Pardo Soares. Pursuit-evasion, decompositions and convexity on graphs. Other [cs.OH]. Université Nice Sophia Antipolis, 2013. English. ⟨NNT : 2013NICE4083⟩. ⟨tel-00908227v2⟩



Record views


Files downloads