Search

We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of n vertices (Ilcinkas and Wade 2018). In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most $O(n\frac {\log n}{\log \log n})$ time units. We show that the lower bound of the algorithm is ${\varOmega }(n\frac {\log n}{(\log \log n)^{2}})$ time units (for infinitely many n).

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

International audience; In this paper, we propose a general scheme, called Algorithm $\mathsf{STlC}$, to compute spanning-tree-like data structures on arbitrary networks. $\mathsf{STlC}$ is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model.Its stabilization time is in $n_{\texttt{maxCC}}$ rounds, where $n_{\texttt{maxCC}}$ is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm $\mathsf{STlC}$.We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, as well as, unconstrained and shortest-path spanning tree constructions.

International audience; This paper investigates compact routing schemes that are very efficient with respect to the memory used to store routing tables in internet-like graphs. We propose a new compact name-independent routing scheme whose theoretically proven average memory per node is upper-bounded by $n^{\gamma}$, with constant $\gamma < 1/2$, while the maximum memory of any node is bounded by $\sqrt{n}$ and the maximum stretch of any route is bounded by~$5$. These bounds are given for the Random Power Low Graphs (RPLG) and hold with high probability. Moreover, we experimentally show that our scheme is very efficient in terms of stretch and memory in internet-like graphs (CAIDA and other maps). We complete this study by comparing our analytic and experimental results to several compact routing schemes. In particular, we show that the average memory requirements is better by at least one order of magnitude than previous schemes for CAIDA maps on 16K nodes.

This thesis focuses on the computation of approximate multicriteria shortest paths. In a multicriteria context, computing the Pareto sets, i.e. all the optimal solutions, is often prohibitive. Many approaches consist in computing only a subset. Some offer reasonable computation times but no guarantee about the representability, i.e. the distribution of the subset output among the whole Pareto set. Others methods guarantee a certain representability and interesting complexities but these are generally unpractical. Another issue is that, strictly speaking, both these approaches usually do not guarantee that the output is really a subset of the Pareto set, i.e. they might output non optimal paths.First, we propose two optimizations of classical exact methods: MC DIJKSTRA 2D for the bicriteria case and BUCKET for higher dimension cases. Then, we propose approximation algorithms with interesting theoretical guarantees. Several of those, SECTOR, SSECTOR and QSSECTOR, work in any dimension and their output sensitive complexity is interesting. The latter being incomparable to the Pareto set size, we propose a 2D optimization, FRAME, which guarantees that the output is only constituted by optimal paths. We deduce that FRAME's complexity is lower or equal to the best known exact computation algorithm. In order to evaluate the pruning capability of FRAME, we conduct an experimental study. This study shows that our algorithm is interesting when the Pareto set sizes are large.In order to accelerate our approximation algorithms in 3D, we study Theta-graphs. We propose efficient algorithms for the dynamic maintenance of these graphs. Then, we study a proximity oriented query, using a Theta-graph to find nearest neighbors in a given direction. Finally, we detail how to apply our Theta-graph algorithms for tricriteria shortest path computation., Cette thèse s'intéresse au calcul de plus courts chemins multicritères approché. Dans un contexte multicritère, le calcul des ensembles de Pareto, c'est-à-dire de toutes les solutions optimales, est souvent prohibitif. De nombreuses approches consistent à n'en calculer que des sous-ensembles. Certaines offrent des temps de calcul raisonnables mais aucune garantie quant à la représentabilité, c'est-à-dire la distribution du sous-ensemble calculé dans l'ensemble de Pareto complet. D'autres méthodes garantissent une certaine représentabilité et des complexités intéressantes, mais elles sont généralement inutilisables en pratique. Un autre problème est que ces deux approches ne garantissent généralement pas que la sortie est réellement un sous-ensemble de l'ensemble de Pareto : elle peut donc contenir des chemins non optimaux.Tout d'abord, nous proposons deux optimisations de méthodes exactes classiques : MC DIJKSTRA 2D pour le cas bicritère et BUCKET pour toute dimension. Ensuite, nous proposons des algorithmes d'approximation avec des garanties théoriques intéressantes. Plusieurs d'entre eux, SECTOR, SSECTOR et QSSECTOR, fonctionnent en dimension quelconque et leur complexité en fonction de la taille de la sortie est intéressante. Cette dernière étant incomparable à la taille de l'ensemble de Pareto, nous proposons une optimisation 2D, FRAME, qui garantit que la sortie n'est constituée que de chemins optimaux. Nous déduisons que la complexité de FRAME est inférieure ou égale à celle du meilleur algorithme de calcul exact connu. Afin d'évaluer la capacité d'élagage de FRAME, nous menons une étude expérimentale. Cette étude montre que notre algorithme est intéressant lorsque la taille des ensembles de Pareto est grande.Afin d'améliorer nos algorithmes d'approximation en 3D, nous étudions les Thêta-graphes. Nous proposons des algorithmes efficaces pour la maintenance dynamique de ces graphes. Ensuite, nous étudions une requête de proximité, utilisant un Thêta-graphe pour trouver les plus proches voisins dans une direction donnée. Enfin, nous détaillons comment appliquer nos algorithmes de Thêta-graphes pour le calcul de plus court chemins tricritères.

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node $u$ stores its distance to all nodes from an appropriately chosen set of hubs $S(u) \subseteq V$. For a queried pair of nodes $(u,v)$, the length of a shortest $u-v$-path passing through a hub node from $S(u)\cap S(v)$ is then used as an upper bound on the distance between $u$ and $v$. We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most $n$ nodes and average degree $\Delta$, the tradeoff between label bit size $L$ and query decoding time $T$ for our approach is given by $L = O(n \log \log_\Delta T / \log_\Delta T)$, for any $T \leq n$. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant $\Delta$, we can achieve any $T=\omega(1)$ while maintaining $L=o(n)$), and it also provides an improvement in terms of label size with respect to previous slower approaches. By using similar techniques, we then present a $2$-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve almost the same label size-time tradeoff $L = O(n \log^2 \log T / \log T)$, for any $T \leq n$. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any $T=\omega(1)$ is sufficient).