In the {\it cops and robber game}, two players play alternately by moving their tokens along the edges of a graph. The first one plays with the {\it cops} and the second one with one {\it robber}. The cops aim at capturing the robber, while the robber tries to infinitely evade the cops. The main problem consists in minimizing the number of cops...
-
2008 (v1)Conference paperUploaded on: December 4, 2022
-
2012 (v1)Journal article
Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks. Two of them are of particular interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose...
Uploaded on: December 3, 2022 -
2009 (v1)Conference paper
We propose a simple interval routing scheme for a graph $G$, based on a Maximal Neighborhood BFS-tree $T$ of $G$. In our scheme a message simply follows the source-destination path in $T$ but, in at most one step, it may take a shortcut. This shortcut is taken when the current node has a neighbor in $G$ which is an ancestor in $T$ of the...
Uploaded on: December 3, 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 -
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 -
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 -
May 7, 2018 (v1)Journal article
Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded...
Uploaded on: December 4, 2022 -
February 2017 (v1)Journal article
We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed $k ≥ 1$, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth...
Uploaded on: February 28, 2023 -
May 11, 2015 (v1)Conference paper
Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms...
Uploaded on: March 25, 2023 -
October 13, 2014 (v1)Report
Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms...
Uploaded on: March 25, 2023 -
2022 (v1)Report
An {\it orientation} $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a {\it $k$-orientation} if the in-degree of each vertex in $D$ is at most $k$. An orientation $D$ of $G$ is {\it proper} if any two adjacent vertices have...
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 -
2012 (v1)Report
A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. In the first...
Uploaded on: December 3, 2022 -
May 20, 2013 (v1)Conference paper
A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual search and the gathering problems. In the first problem, each robot aims...
Uploaded on: December 3, 2022 -
2015 (v1)Journal article
A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In...
Uploaded on: March 25, 2023 -
2023 (v1)Conference paper
An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper...
Uploaded on: November 30, 2023 -
2011 (v1)Conference paper
Nous étudions quelles propriétés d'un réseau peuvent être calculées à partir d'une petite quantité d'informations locales fournie par ses noeuds. Notre modèle est une restriction de CONGEST, un modèle distribué classique. Il est proche du modèle de complexité de communication avec messages simultanés de Babai et al. Chacun des n noeuds --qui ne...
Uploaded on: December 3, 2022 -
September 2010 (v1)Report
In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...
Uploaded on: February 22, 2023 -
2010 (v1)Journal article
The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question. In this paper we prove that computing...
Uploaded on: December 3, 2022 -
2011 (v1)Conference paper
In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...
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