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$....
-
February 2010 (v1)ReportUploaded on: December 4, 2022
-
2012 (v1)Conference paper
Nous présentons un algorithme quadratique qui, étant donné un graphe $G$ et un entier $k\geq 3$, certifie que $G$ contient un cycle induit de longueur $>k$, ou calcule une décomposition arborescente de $G$ dont chaque ''sac" induit un $k$-caterpillar (graphe qui contient un chemin dominant, de longueur au plus $k-2$). Entre autre, ce résultat...
Uploaded on: December 3, 2022 -
February 2012 (v1)Report
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$. We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs. This leads us to our main result, a new...
Uploaded on: December 3, 2022 -
2010 (v1)Conference paper
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...
Uploaded on: December 3, 2022 -
2015 (v1)Journal article
Cops and robber games, introduced by Winkler and Nowakowski [41] and independently defined by Quilliot [43], concern a team of cops that must capture a robber moving in a graph. We consider the class of k-chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, k ≥ 3. We prove that k − 1 cops are always...
Uploaded on: March 25, 2023 -
2012 (v1)Conference paper
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$. We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs. This leads us to our main result, a new...
Uploaded on: December 4, 2022 -
July 2010 (v1)Conference paper
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...
Uploaded on: December 3, 2022 -
2012 (v1)Conference paper
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$. We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs. This leads us to our main result, a new...
Uploaded on: February 22, 2023 -
2012 (v1)Conference paper
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph-theoretic...
Uploaded on: December 4, 2022 -
2011 (v1)Report
In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the...
Uploaded on: December 3, 2022 -
2015 (v1)Journal article
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes...
Uploaded on: March 25, 2023