Search

In highly dynamic systems (such as wireless mobile ad hoc networks, robotic swarms, vehicular networks, etc.) connectivity does not necessarily hold at a given time but temporal paths, or journeys, may still exist over time and space, rendering computing possible; some of these systems allow waiting (i.e., pauses at intermediate nodes, also referred to as store-carry-forward strategies) while others do not. These systems are naturally modeled as time-varying graphs, where the presence of an edge and its latency vary as a function of time; in these graphs, the distinction between waiting and not waiting corresponds to the one between indirect and direct journeys.We consider the expressivity of time-varying graphs, in terms of the languages generated by the feasible journeys. We examine the impact of waiting by studying the difference in the type of language expressed by indirect journeys (i.e., waiting is allowed) and by direct journeys (i.e., waiting is unfeasible), under various assumptions on the functions that control the presence and latency of edges. We prove a general result which implies that, if waiting is not allowed, then the set of languages Lnowait that can be generated contains all computable languages when the presence and latency functions are computable. On the other end, we prove that, if waiting is allowed, then the set of languages Lwait contains all and only regular languages; this result, established using algebraic properties of quasi-orders, holds even if the presence and latency are unrestricted (e.g., possibly non-computable) functions of time.In other words, we prove that, when waiting is allowed, the power of the accepting automaton can drop drastically from being at least as powerful as a Turing machine, to becoming that of a Finite-State Machine. This large gap provides an insight on the impact of waiting in time-varying graphs.We also study bounded waiting, in which waiting is allowed at a node for at most d time units, and prove that Lwait[d]=Lnowait; that is, the power of the accepting automaton decreases only if waiting time is unbounded.

Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called journeys). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), and foremost (earliest arrival) journeys. Efficient centralized algorithms exists to compute all cases, when the full knowledge of the network evolution is given. In this paper, we study the distributed counterparts of these problems, i.e. shortest, fastest, and foremost broadcast with termination detection (TDB), with minimal knowledge on the topology. We show that the feasibility of each of these problems requires distinct features on the evolution, through identifying three classes of dynamic graphs wherein the problems become gradually feasible: graphs in which the re-appearance of edges is recurrent (class [Formula: see text]), bounded-recurrent ([Formula: see text]), or periodic ([Formula: see text]), together with specific knowledge that are respectively n (the number of nodes), Δ (a bound on the recurrence time), and p (the period). In these classes it is not required that all pairs of nodes get in contact — only that the overall footprint of the graph is connected over time. Our results, together with the strict inclusion between [Formula: see text], [Formula: see text], and [Formula: see text], implies a feasibility order among the three variants of the problem, i.e. TDB[foremost] requires weaker assumptions on the topology dynamics than TDB[shortest], which itself requires less than TDB[fastest]. Reversely, these differences in feasibility imply that the computational powers of [Formula: see text], [Formula: see text], and [Formula: see text] also form a strict hierarchy.

International audience; We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line. For k= 5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.

International audience; We describe and evaluate a pre-processing method based on a periodic spiral sampling of diffusion-gradient directions for high angular resolution diffusion magnetic resonance imaging. Our pre-processing method incorporates prior knowledge about the acquired diffusion-weighted signal, facilitating noise reduction. Periodic spiral sampling of gradient direction encodings results in an acquired signal in each voxel that is pseudo-periodic with characteristics that allow separation of low-frequency signal from high frequency noise. Consequently, it enhances local reconstruction of the orientation distribution function used to define fiber tracks in the brain. Denoising with periodic spiral sampling was tested using synthetic data and in vivo human brain images. The level of improvement in signal-to-noise ratio and in the accuracy of local reconstruction of fiber tracks was significantly improved using our method.

International audience; In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on ''the price of connectivity'', that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an $n$-vertex graph the ratio between the connected searching number and the non-connected one is $O(\log n)$ while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Stralher number.