Search

This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large. We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm., OASIcs, Vol. 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), pages 11:1-11:19

Rapporteur non membre du jury : Evangelos Kranakis; This manuscript presents a significant part of my research results in the past years, in the field of distributed computing in networks. The document is structured from the point of view of information available to the computing entities. First, I present my results concerning the advice framework, which allows to study quantitative questions about the a priori information given to the computing entities in order to solve a given problem. I address then the geometric setting, where the computing entities are mobile robots that acquire information about their environment through vision. The third part concerns the exploration of dynamic networks by a mobile entity (called agent in this context), and the impact of knowing the future topological changes. The next part also deals with distributed computing by mobile agents and considers various problems and the different ways of storing information on the network. Finally, the last group of presented results focuses on a particular type of information, the routing one, useful in many contexts to efficiently transfer information in a network.

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes., Discrete Mathematics & Theoretical Computer Science ; Vol. 19 no. 3 ; 1365-8050

International audience; Nous considérons les problèmes de décision qui sont résolus de manière répartie par des agents mobiles synchrones évoluant dans un réseau inconnu et anonyme. Chaque agent dispose d'un identifiant unique et d'une chaîne d'entrée, et ces agents doivent décider collectivement de la validité d'une propriété qui peut être basée sur les chaînes d'entrée, le graphe dans lequel les agents évoluent, et leurs positions de départ. Poursuivant un travail récent de Friagniaud et Pelc [LATIN 2012, LNCS 7256, p. 362–374], nous introduisons plusieurs nouvelles classes naturelles de calculabilité par agents mobiles, nous permettant d'obtenir une classification plus fine des problèmes inclus dans co-MAV ou MAV, cette dernière étant la classe des problèmes vérifiables lorsque les agents disposent d'un certificat approprié. Dans cet article, nous exhibons des résultats d'inclusion ou de séparation entre toutes ces classes. Nous déterminons également leurs propriétés de clôture vis-à-vis des opérations classiques de la théorie des ensembles. Notre principal outil technique, intéressant en soi, est un nouveau méta-protocole qui permet l'exécution essentiellement en parallèle d'un nombre potentiellement infini de protocoles d'agents mobiles, de façon similaire à la technique classique de déployeur universel (dovetailing) présente en calculabilité classique.

Many articles deal with the problem of maintaining a rooted shortest-path tree. However , after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r. In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r. We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous networks with the following properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2n + D rounds for a network of n nodes and hop-diameter D.

International audience

International audience; Cet article étudie les schémas de routage compacts qui sont très efficaces en termes de mémoires utilisées pour le stockage des tables de routage dans les graphes de type Internet. Nous proposons un nouveau schéma de routage compact avec indépendance des noms, dont la mémoire moyenne par noeud est prouvée comme étant bornée par √n, et pour lequel l'étirement maximum de toute route est au plus 7. Ces bornes sont données pour la classe RPLG (Random Power Low Graphs) et sont vraies avec forte probabilité. De plus, nous montrons expérimentalement que notre schéma est tr es efficace en termes d'étirement et de mémoire dans les graphes de type Internet (CAIDA et d'autres cartes). Nous complétons cette étude en comparant nos résultats analytiques et expérimentaux a plusieurs schémas de routage compact. En particulier, nous montrons que les besoins moyens en mémoire de notre schéma sont meilleurs que les schémas précédents d'au moins un ordre de grandeur pour des cartes CAIDA de 16K noeuds.

International audience; Nous étudions le problème de l'exploration, par une entité mobile, d'une classe de graphes dynamiques appelés graphes périodiquement variables (PV-graphes). Ils sont définis par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau, et modélisent donc naturellement les réseaux de transport public. Flocchini, Mans et Santoro [FMS09] ont étudié ce problème dans le cas où l'agent doit toujours rester sur les transporteurs. Dans ce papier, nous étudions l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins Theta(p), et la complexité en temps passe de Theta(kp^2) à Theta(np), où n est le nombre de stations, k le nombre de transporteurs, et p la période maximale (n

International audience; Pour permettre le routage dans un graphe, les nœuds doivent connaître des portions de route. La dynamique du graphe peut rendre les informations stockées erronées. Cet article s'intéresse à la caractérisation de la quantité d'informations erronées, ainsi qu'aux nombre de changements de distances dans le graphe suite à L suppressions d'arêtes et L' suppressions de nœuds. Nous considérons un graphe G de diamètre D possédant N nœuds et M arêtes. Nous montrons que l'espérance du nombre d'erreurs et de changement de distance est d'au plus D (LN/M + L').

International audience; The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game.

Graph Exploration is a problem motivated by several aspects of theoretical computer science, including logic and computational complexity. It has also numerous applications in robotics. In all these contexts, the amount of memory used by the mobile entity (robot, finite automaton, etc.) performing exploration is a key parameter. In this thesis, we study in depth the space complexity of graph exploration, in two different frameworks.In the first part of the thesis, we focus on exploration "without assistance", i.e., the case where the mobile entity does not possess any a priori information about the explored graph. In this context, we prove several lower and upper bounds on the amount of memory necessary and sufficient to the mobile entity for performing exploration of all graphs. In particular, we show that the depth-first search algorithm is optimal in space when the complexity is measured in term of degree and diameter.In the second part of the thesis, we focus on exploration "with assistance", by assuming that an oracle entirely aware of the input graph can help the mobile entity, by providing some information about it. This information is measured by its bit-space complexity, and we are interested in the minimal number of bits that the oracle must provide so that the mobile entity can perform exploration. The information can be either given directly to the entity, or encoded on the vertices of the graph., Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement d'un étiquetage global. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à traverser chacun des liens du réseau. Nous montrons que, pour tout robot à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ nœuds que le robot ne réussit pas à explorer. Cette borne $K+1$ améliore toutes les bornes connues jusqu'aujourd'hui. Nous montrons également que, pour explorer tous les graphes de diamètre $D$ et de degré maximum $d$, un robot doit disposer de $\Omega(D\log{d})$ bits de mémoire, et ce même si l'on restreint l'exploration aux réseaux planaires. Enfin, nous montrons que cette borne est asymptotiquement optimale, en décrivant un algorithme qui permet à un robot possédant une mémoire de $O(D\log{d})$ bits d'explorer tous les réseaux de diamètre $D$ et de degré maximum $d$. Ceci nous permet donc de conclure que la complexité mémoire du problème de l'exploration de réseaux est $\Theta(D\log{d})$ bits.

International audience; Nous présentons un algorithme distribué construisant des tables de routage de taille sous-linéaire en n, le nombre de nœuds du réseau. Le temps de convergence est proportionnel au diamètre, ce qui est optimal. Par rapport à BGP, la complexité du nombre de messages échangés est améliorée jusqu'à un facteur n^1/2, alors que la longueur des routes induites par les tables est allongée d'un facteur garanti constant. Notre algorithme est conçu pour un environnement statique synchrone ou asynchrone et produit un schéma name-independent.

International audience; 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 nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2^Ω(min{d,k}), for any d,k = O(log n), even when G is a tree. This paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The strategy which we put forward, called R/A, makes use of a timer (step counter) to alternate between phases of ignoring advice (R) and following advice (A) for a certain number of steps. No knowledge of parameters n, d, or k is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random Δ-regular graphs (an important class of expanders). For the ring, R/A is shown to achieve an expected searching time of 2d+k^Θ(1) for a worst-case distribution of liars, which is polynomial in both d and k. For random Δ-regular graphs, the expected searching time of the R/A strategy is O(k^3 log^3 n) a.a.s. The polylogarithmic factor with respect to n cannot be dropped from this bound; in fact, we show that a lower time bound of Ω(log n) steps holds for all d,k = Ω(log logn) in random Ω-regular graphs a.a.s. and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the R/A strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in d and k.

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$. Unfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. It is known that for an $n$-node graph $G$ of maximum degree $\Delta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\Omega(\min\{d,k\})}$, for any $d,k=O(\log n)$, even when $G$ is a tree. This paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The strategy which we put forward, called \algo{R/A}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{R}) and following advice (\algo{A}) for a certain number of steps. No knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). For the ring, \algo{R/A} is shown to achieve an expected searching time of $2d+k^{\Theta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. For random $\maxdeg$-regular graphs, the expected searching time of the \algo{R/A} strategy is $O(k^3 \log^3 n)$ a.a.s. The polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\Omega (\log n)$ steps holds for all $d,k=\Omega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the \algo{R/A} strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$

International audience; Cet article concerne les graphes de recouvrement d'un ensemble fini de points du plan Euclidien. Un graphe de recouvrement $H$ est de facteur d'étirement $t$ pour un ensemble de points $S$ si, entre deux points quelconques de $S$, le coût d'un plus court chemin dans $H$ est au plus $t$ fois leur distance Euclidenne. Les graphes de recouvrement d'étirement $t$ (ci-après nommés \emph{$t$-spanneurs}) sont à la base de nombreux algorithmes de routage et de navigation dans le plan. Le graphe (ou triangulation) de Delaunay, le graphe de Gabriel, le graphe de Yao ou le Theta-graphe sont des exemples bien connus de $t$-spanneurs. L'étirement $t$ et le degré maximum des spanneurs sont des paramètres important à minimiser pour l'optimisation des ressources. En même temps le caractère planaire des constructions se révèle essentiel dans les algorithmes de navigation. Nous présentons une série de résultats dans ce domaine, en particulier: \begin{itemize} \item Nous montrons que le graphe $\Theta_6$ (le Theta-graphe où $k=6$ cônes d'angle $\Theta_k = 2\pi/k$ par sommet sont utilisées) est l'union de deux spanneurs planaires d'étirement deux. En particulier, nous établissons que l'étirement maximum du graphe $\Theta_6$ est deux, ce qui est optimal. Des bornes supérieures sur l'étirement du graphe $\Theta_k$ n'étaient connues que lorsque $k > 6$. Pour $k=7$, la meilleure borne connue est d'environ $7.56$ et pour $k=6$ il était ouvert de savoir si le graphe était un $t$-spanneur pour une valeur constante de $t$. \item Nous montrons que le graphe $\Theta_6$ contient comme sous-graphe couvrant un $3$-spanneur planaire de degré maximum au plus~$9$. \item Finalement, en utilisant une variante du résultat précédant, nous montrons que le plan Euclidien possède un $6$-spanneur planaire de degré maximum au plus~$6$. \end{itemize} La dernière construction, non décrite ici par manque de place, améliore une longue série de résultats sur le problème largement ouvert de déterminer la plus petite valeur $\delta$ telle que tout ensemble du plan possède un spanneur planaire d'étirement constant et de degré maximum $\delta$. Le meilleur résultat en date montrait que $3 \le \delta\le 14$.

International audience; 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 et de degré maximum Delta >= 3, atteindre une cible à distance d de la position initiale peut demander un temps moyen de 2^{Omega(min{d,k})}, pour tout d,k=O(log n), même lorsque G est un arbre. Ce papier étudie une stratégie, appelée R/A, utilisant un compteur (d'étapes) pour alterner entre les phases aléatoires (R) où l'agent choisit aléatoirement une arête incidente, et celles (A) où l'agent suit le conseil local. Aucune connaissance des paramètres n, d, ou k n'est requise, et l'agent n'a pas besoin de se rappeler par quel lien il est entré dans le sommet qu'il occupe. Nous étudions les performances de cette stratégie pour deux classes de graphes, extrêmes pour ce qui est de l'expansion: les anneaux et les graphes réguliers aléatoires (une importante classe d' expanders). Pour l'anneau, l'algorithme R/A requiert un temps moyen de 2d+k^{Theta(1)} (polynomial en d et k) pour une distribution des menteurs la plus défavorable. A l'opposé, nous montrons que dans un anneau, une marche aléatoire biaisée requiert un temps moyen exponentiel en d et k. Pour les graphes aléatoires réguliers, le temps de recherche moyen de l'algorithme R/A est O(k^3 log^3 n) a.a.s.\ Le terme polylogarithmique de cette borne ne peut pas être amélioré, puisque nous montrons une borne inférieure de Omega(log n) pour d,k=Omega(log log n) dans les graphes aléatoires réguliers a.a.s. qui s'applique même lorsque l'agent a le sens de l'orientation.

National audience; Un trou noir est un noeud d'un réseau qui détruit tout agent (ou robot) y entrant sans laisser de trace détectable. L'emplacement du trou noir doit être déterminé par une une équipe d'agents mobiles identiques déployée à partir d'un emplacement sain. Pratiquement tous les résultats existants pour des agents asynchrones supposent la présence à chaque noeud d'une mémoire partagée (tableau blanc), de taille logarithmique, sur laquelle les agents peuvent lire et écrire. Un méchanisme moins puissant et moins exigeant consiste en l'utilisation de cailloux identiques (qui peuvent être déposés sur les noeuds, repris, et transportés par les agents), traditionnellement employés pour l'exploration de graphes sains (i.e. sans trou noir). Deux résultats récents montrent qu'il est possible d'utiliser des cailloux comme moyen de communication pour la recherche de trou noir. Ces résultats autorisent cependant les cailloux à être placés non seulement sur les noeuds mais aussi sur les liens. Ils supposent également que les liens sont FIFO. Dans ce papier, nous considérons le modèle des cailloux idéaux, c'est-à-dire le modèle où un caillou ne peut être placé que sur les noeuds, et pas plus d'un caillou ne peut être placé sur un noeud donné. Nous prouvons que pour les réseaux de topologie connue il est possible d'obtenir exactement les mêmes bornes optimales en utilisant des cailloux idéaux qu'en utilisant des tableaux blancs, et ce même si les liens ne sont pas FIFO. Plus précisément, nous prouvons qu'une équipe de deux agents asynchrones, chacun équipé d'un seul caillou indistinguable (qui ne peut être placé que sur les noeuds, avec au plus un caillou par noeud), peut localiser le trou noir. Ce résultat est obtenu en utilisant le nombre optimal de mouvements $\Theta(n\log{n})$, où n est le nombre de noeuds. Pour résumer, nous fournissons la première preuve que, pour la recherche de trou noir, le modèle des cailloux idéaux est aussi puissant que le modèle des tableaux blancs.

National audience; L'encerclement dans les réseaux vise à réaliser le nettoyage, par une équipe d'agents mobiles, d'un réseau contaminé. La stratégie d'encerclement est calculée en temps réel, par les agents eux mêmes, et doit vérifier les trois propriétés suivantes : (1) connexité : la zone nettoyée doit toujours être connexe de façon à assurer des communications sécurisées entre les agents, (2) monotonie : la zone nettoyée ne doit jamais être recontaminée, ce qui permet un temps de nettoyage polynomial en la taille du réseau, et (3) optimalité : le nombre d'agents utilisés doit être le plus petit possible afin de minimiser la taille des ressources utilisées. Etant donné un graphe G, le plus petit nombre d'agents nécessaire pour nettoyer G de façon monotone connexe dans un contexte centralisé est noté mcs(G). Plusieurs protocoles répartis ont été proposés pour résoudre le problème de l'encerclement dans les réseaux. Blin et al. ont proposé un algorithme distribué permettant à mcs(G) agents de déterminer et de réaliser une stratégie d'encerclement dans tout graphe inconnu G (inconnu signifie que les agents n'ont aucune connaissance a priori concernant le graphe) [AlgoTel'06]. Cependant, la stratégie réalisée n'est pas monotone et peut prendre un temps exponentiel. Nisse et Soguet ont prouvé que, pour résoudre le problème de l'encerclement dans les réseaux, il est nécessaire et suffisant de fournir $\Theta(n\log{n})$ bits d'information aux agents par le biais d'un étiquetage des sommets du graphe [AlgoTel'07]. Ainsi, pour nettoyer un graphe inconnu de façon monotone et connexe, il est nécessaire d'utiliser plus d'agents que l'optimal. Dans cet article, nous étudions la proportion d'agents supplémentaires qui sont nécessaires et suffisants pour nettoyer de façon monotone connexe répartie tout graphe inconnu. Nous montrons que la contrainte de monotonie implique une augmentation drastique de ce nombre d'agents. Nous prouvons que tout protocole distribué ayant pour but de nettoyer tout graphe inconnu de n sommets de façon monotone connexe répartie a un ratio compétitif de $\Theta(n/\log{ n})$. Plus précisément, nous prouvons que pour tout protocole distribué P, il existe une constante c tel que pour tout n suffisamment grand, il existe un graphe G de n sommets tel que P requiert au moins $c.n/\log{ n}$ mcs(G) agents pour nettoyer G. De plus, nous proposons un protocole distribué qui permet à $O(n/\log{ n})$ mcs(G) agents de nettoyer tout graphe inconnu G de n sommets, de façon monotone connexe répartie.

National audience; Une équipe d'entités mobiles (robots), identiques et sans mémoire, doit explorer un arbre anonyme en visitant tous ses noeuds. Les robots démarrent depuis des noeuds différents et arbitraires de l'arbre et opèrent suivant des cycles Regarder-Calculer-Aller (Look-Compute-Move). A la fin, chaque noeud doit avoir été visité par au moins un robot, et tous les robots doivent s'arrêter. Dans un cycle, un robot prend une photographie de la configuration courante (Regarder), prend la décision de rester immobile ou de se déplacer vers un des noeuds adjacents (Calculer), et dans ce dernier cas se déplace instantanément vers ce voisin (Aller). Les cycles sont exécutés de façon asynchrone par chaque robot. Nous présentons un algorithme d'exploration pour tous les arbres à n noeuds de degré maximum 3 utilisant O(log n/loglog n) robots, et nous prouvons que pour de tels arbres Omega(log n/loglog n) robots sont nécessaires pour les explorer. Nous montrons par ailleurs que l'exploration de certains arbres à n noeuds de degré maximum 4 nécessite Omega(n) robots.

National audience; Nous étudions la quantité de connaissance nécessaire sur le réseau pour résoudre efficacement une tâche sur celui-ci. L'impact de l'information disponible sur l'efficacité de la résolution des problèmes, comme la communication ou l'exploration, a déjà été étudié auparavant mais les hypothèses concernaient la disponibilité d'informations {\em particulières} sur le réseau, comme sa taille, son diamètre ou une carte de celui-ci. Au contraire, notre approche est {\em quantitative} : nous étudions le nombre minimum de bits d'information (taille d'oracle minimum) qui doivent être fournis à l'algorithme pour effectuer une tâche avec une certaine efficacité. Nous illustrons cette approche quantitative de l'information disponible par le problème de l'exploration d'arbres. Une entité mobile (robot) doit traverser toutes les arêtes d'un arbre inconnu, en utilisant aussi peu de traversées d'arêtes que possible. La qualité d'un algorithme d'exploration $\cA$ est mesuré par son {\em rapport compétitif}, i.e., par comparaison de son coût (nombre de traversées d'arêtes) à la longueur du plus court chemin contenant toutes les arêtes de l'arbre. Le parcours en profondeur d'abord a un rapport compétitif de 2 et en l'absence d'information sur l'arbre aucun algorithme ne peut faire mieux. Nous déterminons le nombre minimal de bits d'information qui doit être donné à un algorithme d'exploration afin d'obtenir un rapport compétitif strictement plus petit que 2. Notre résultat principal établit un seuil exact sur la taille de l'oracle, qui est approximativement $\log \log D$ bits, où $D$ est le diamètre de l'arbre. Plus précisément, pour toute constante $c$, nous construisons un algorithme d'exploration de rapport compétitif plus petit que 2, utilisant un oracle de taille au plus $\log \log D -c$, et nous montrons que tout algorithme utilisant un oracle de taille $\log \log D -g(D)$, pour toute fonction $g$ non bornée supérieurement, a un rapport compétitif au moins égal à 2.

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à explorer chacun des n{\oe}uds du réseau. Il a été montré que, pour tout robot $\cR$ à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ n{\oe}uds que $\cR$ ne réussit pas à explorer. Ce papier s'intéresse à la possibilité d'aider le robot en ajoutant des étiquettes de petite taille aux n{\oe}uds grâce à un calcul préalable. Nous décrivons un algorithme d'exploration qui, étant donné des étiquettes appropriées sur 2~bits (en fait des étiquettes de trois valeurs différentes), permet à un robot d'explorer tous les réseaux. De plus, nous décrivons un algorithme linéaire calculant un tel étiquetage. Nous montrons également comment modifier notre méthode d'étiquetage afin qu'un robot puisse explorer tous les réseaux de degré constant, avec des étiquettes de seulement 1~bit (donc des étiquettes de deux valeurs différentes seulement). Autrement dit, alors qu'il n'existe pas de robot capable d'explorer tous les réseaux (non étiquetés) de degré maximum~3, il existe un robot $\cR^*$ et un moyen de colorier les n{\oe}uds en noir et blanc tel que $\cR^*$ réussit à explorer tous les réseaux coloriés de degré maximum~3.

International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and $n+ \frac {n}{\max \{1, T-1\} } (\delta -1) \pm {\Theta }(\delta )$ time units otherwise, where δ is the maximum time between two successive appearances of an edge.