NISSE , Nicolas

This manuscript describes the work I did since I obtained my Ph.D. in 2007. In addition to the presentation of my contributions, I tried to give overviews of the scienti c areas my work takes part of and some of the main issues that arise here. My work deals with new algorithmic challenges posed by the growth of nowadays networks and by the...

Ces posters font partie d'une série de posters que nous présentons lors de divers interventions de médiation (vulgarisation) scientifique (Fête de la Science, intervention dans des écoles, etc.). Nous essayons d'y présenter des bases théoriques (mathématiques) de l'algorithmique (Un algorithme est une suite finie et non ambiguë d'opérations ou...

Ces posters font partie d'une série de posters que nous présentons lors de divers interventions de médiation (vulgarisation) scientifique (Fête de la Science, intervention dans des écoles, etc.). Nous essayons d'y présenter des bases théoriques (mathématiques) de l'algorithmique (Un algorithme est une suite finie et non ambiguë d'opérations ou...

Ces posters font partie d'une série de posters que nous présentons lors de divers interventions de médiation (vulgarisation) scientifique (Fête de la Science, intervention dans des écoles, etc.). Nous essayons d'y présenter des bases théoriques (mathématiques) de l'algorithmique (Un algorithme est une suite finie et non ambiguë d'opérations ou...

We propose a fractional relaxation of two-player combinatorial games. Two players can move or/and add fractions of tokens on the nodes of a graph and a player wins if he is the first one to reach a configuration in some specified set. Both allowed moves and winning configurations are defined thanks to linear inequalities. Our framework applies...

We propose a fractional relaxation of two-player combinatorial games. Two players can move or/and add fractions of tokens on the nodes of a graph and a player wins if he is the first one to reach a configuration in some specified set. Both allowed moves and winning configurations are defined thanks to linear inequalities. Our framework applies...

The Network Decontamination problem consists of coordinating a team of mobile agents in order to clean a contaminated network. The problem is actually equivalent to tracking and capturing an invisible and arbitrarily fast fugitive. This problem has natural applications in network security in computer science or in robotics for search or...

Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426--441]: given a "contaminated†graph G (e.g., a network containing a hostile intruder), the search number View the MathML source of the graph G is the minimum...

Il s'agit du premier volet d'une série de posters que nous présentons lors de divers interventions de médiation (vulgarisation) scientifique (Fête de la Science, intervention dans des écoles, etc.). Nous essayons d'y présenter des bases théoriques (mathématiques) de l'algorithmique (Un algorithme est une suite finie et non ambiguë d'opérations...

The Network Decontamination problem consists in coordinating a team of mobile agents in order to clean a contaminated network. The problem is actually equivalent to tracking and capturing an invisible and arbitrarily fast fugitive. This problem has natural applications in network security in computer science or in robotics for search or...

The Network Decontamination problem consists of coordinating a team of mobile agents in order to clean a contaminated network. The problem is actually equivalent to tracking and capturing an invisible and arbitrarily fast fugitive. This problem has natural applications in network security in computer science or in robotics for search or...

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...

We study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse {\it et al.}~\cite{HKK00,HKKK08}. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$....

Nous étudions le problème consistant à trouver une destination t dans un réseau, non fiable, grâce à un agent mobile. Chaque noeud du réseau peut donner un conseil quant au prochain sommet à visiter pour se rapprocher de t. Malheureusement, k noeuds, appelés menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommets...

We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the...

The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ∈ N, Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • • , k} such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob...

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...

A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by pl(G), of G is the smallest length of its path-decompositions....

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...

Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of...

Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree- and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a...

We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This implies that there is a polynomial time algorithm to compute the convex hull number of a graph, when all its convex subgraphs are given as input. We then show that deciding if the smallest...

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70--84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of...

Fraigniaud {\it et al.} (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest {\it number of bits of advice} of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of...