FRAIGNIAUD , Pierre

Le problème de l'encerclement dans les réseaux a été introduit par Parson (1976) : étant donné un réseau ``contaminé'' (par exemple dans lequel un intrus s'est introduit), l'emph{encerclement} du réseau est le nombre minimum d'agents nécessaires pour ``nettoyer'' le réseau (c'est-à-dire capturer l'intrus). Une stratégie d'encerclement est dite...

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that...

We give a constructive proof of the equality between \emph{treewidth} and \emph{connected treewidth}. More precisely, we describe an $O(nk^3)$-time algorithm that, given any $n$-node width-$k$ tree-decomposition of a connected graph $G$, returns a connected tree-decomposition of $G$ of width $\leq k$. The equality between treewidth and...

Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman, Haeupler, and Korman [PODC 2014] that complex...

Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask...

International audience

International audience

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which...

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which...

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which...

International audience

Nous définissons l'encerclement non-déterministe dans les graphes. Nous montrons comment ce nouvel outil peut être utilisé pour la conception d'algorithmes et pour l'analyse combinatoire de la largeur linéaire (pathwidth) comme de la largeur arborescente (treewidth) des graphes. Nous prouvons l'équivalence entre cette approche sous forme de...

Junta de Andalucía

This paper addresses the graph searching problem in a distributed setting.We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without...

International audience

No description

International audience

Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at cap- turing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit- evasion game or cops...

Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at capturing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit-evasion game or cops and...

In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the...

In graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the...

"Communication dans les réseaux de processeurs" écrit sous le nom de jean de Rumeur