Programme
Mercredi 23 novembre
- 18h-20h - Arrivée des participants
- 20h30 - Dîner
Jeudi 24 novembre
-
9h00 - (LaBRI)
Introduction to temporal graphs (and presentation of the project) [slides]
-
10h00 - (LaBRI)
Self-stabilizing Systems in Spite of High Dynamics [slides]We initiate research on self-stabilization in highly dynamic message-passing systems by addressing the self-stabilizing leader election problem in three wide classes of time-varying graphs (TVGs): the class of TVGs with temporal diameter bounded by Delta (boundDiam), the class of TVGs with temporal diameter quasi-bounded by Delta (quasiBoundDiam), and the class of TVGs with recurrent connectivity only (recur). We first study conditions under which our problem can be solved. We introduce the notion of size-ambiguity to show that the assumption on the knowledge of the number nof processes is crucial. Our results show that any deterministic self-stabilizing leader election algorithm working in the class quasiBoundDiam or recur cannot be size-ambiguous, justifying then the necessity of assuming the exact knowledge of network size in those classes. We then present three self-stabilizing leader election algorithms for Classes boundDiam, quasiBoundDiam, and recur, respectively. Our algorithm for boundDiam stabilizes in at most 3.Delta rounds. In quasiBoundDiam and recur, stabilization time cannot be bounded. However, we show that our solutions are speculative in the sense that their stabilization time in boundDiam is O(Delta) rounds. This is joint work with Karine Altisen, Stéphane Devismes, Anaïs Durand, and Franck Petit (ICDCN 2021)
- 10h30 - Pause café
-
11h00 - (IRIF)
Walk temporalisation [slides]In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation. We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order.
-
11h30 - (LITIS)
Components in temporal graphs [slides]Temporal graphs are graphs in which edges can appear and disappear over time. We partly answer the question ``What does a connected component correspond to in temporal graphs?'' Indeed, many forms of connectivity exist in temporal graphs, some of which are defined with journeys, \textit{i.e.} composed of successive edges in time. We present some results concerning components defined with journeys. After a general introduction presenting among other things the hierarchy of temporal connectivity and its implications, we study $\mathcal{S}$ components, where there is a source vertex which can reach all the other vertices of the component with journeys. Structural and algorithmic results are given. We generalize by considering sliding time windows, closed components (journeys remain inside the component), and/or allowing the source to change between windows. Finally, we complete results concerning $\mathcal{TC}$ components, where each node must reach each other node, and its generalizations. We study more finely the complexity concerning fixed parameters, and we present an algorithm adapted for closed components.
-
12h00 - (LaBRI)
Computing parameters of sequence-based dynamic graphs [slides]We present a general framework for computing parameters of dynamic networks which are modeled as a sequence ( G1, G2, ..., Gδ ) of static graphs such that Gi = ( V, Ei ) represents the network topology at time i and changes between consecutive static graphs are arbitrary. The framework operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a "composition" operation and a "test" operation. The framework allows us to compute different parameters of dynamic graphs using a common high-level strategy by using composition and test operations that are specific to the parameter. The resulting algorithms are optimal in the sense that they use only O(δ) composition and test operations, where δ is the length of the sequence. We illustrate our framework with three minimization problems, namely "bounded realization of the footprint", "temporal diameter", and "round trip temporal diameter", as well as with one maximization problem, namely "T-interval connectivity". We prove that the problems are in the class NC by presenting polylogarithmic-time parallel versions of the algorithms. Finally, we show that the algorithms can operate online with amortized complexity Θ(1) composition and test operations for each graph in the sequence. This is joint work with Arnaud Casteigts, Yessin M. Neggaz, and Joseph G. Peters.
- 12h30 - Déjeuner
-
14h30 - (LITIS)
An Illustrative Case Study of Dynamic Graphs Generators AnalysisAfter positioning our work within the Tempogral project, this talk will focus on the analysis of generators. Some generators are characterized by an unknown evolution function of the number of vertices, which raises some new questions about their analysis. For that purpose, we introduce a new qualitative notion, the sustainability, and a new metric, the nervousness. We then propose a new generative model to illustrate their use: D3G3 (standing for Degree-Driven Dynamic Geometric Graphs Generator).
-
15h00 - (LaBRI)
Introduction to mobile data structuresDans cet exposé, je présenterai la problématique des structures de données mobiles, dont le but est de maintenir des informations spatiales (p.ex. l'enveloppe convexe) sur des entités mobiles, d'une façon peu coûteuse.
-
15h30 - (LaBRI)
On the Freeze-Tag Problem [slides]We consider the problem of awaking as fast as possible and by contacts a swarm of asleep robots, starting with only one awake robot. In this talk, we will review main results for this problem, in particular for the euclidean plane, and also give some recent contributions. This is a joint work with Nicolas Bonichon, Arnaud Casteigts, and Nicolas Hanusse.
- 16h00 - Pause café
-
16h30 - (LIA)
Flows in temporal graphs: solving methods and open questions
-
17h00 - (IRIF)
Algorithmic aspects of graph classes with certificates using patterns [slides]Graph classes usually are defined by excluding minors or subgraphs, here we consider hereditary graph classes that can be characterized by the existence of an ordering of the vertices avoiding a set of patterns. First we recall known results for sets of patterns on 3 nodes that yield interval (resp. chordal, comparability ....) graphs classes. We then extend the problem to patterns on 4 nodes with a particular interest for graph classes that can be defined as the intersection of "geometric" objects. To conclude we will discuss the algorithmic difference between finding a good ordering of the vertices and checking it. This patterns approach could perhaps be used to classify temporal graph classes. Joint work with L. Feuilloley (LIRIS Lyon).
- 18h00 -
- 20h - dîner
Vendredi 25 novembre
-
9h00 - (IRIF)
Recoloring in temporal graphsA temporal graph can be informally described as a graph whose connections change with time. Thus, a specific coloring may no longer be proper when new edges appear. It naturally raises a question about reconfiguration of coloring in temporal graphs. We propose different definitions for Coloring and Recoloring Problems in Temporal Graphs. We then study upper bounds on the number of colors needed to (re)color temporal graphs in general and restrictive situations when subgraphs are trees, $d$-degenerate graphs, $\Delta$-bounded graphs.
-
9h30 - (IRIF)
Min-Cost Temporal Walks under Waiting-Time Constraints in Linear TimeIn a temporal graph, each edge is available at specific points in time. Such an availability is often represented by a ``temporal edge'' that can be traversed from its tail only at a specific departure time, for arriving in its head after a specific travel time. In such a graph, the connectivity from one node to another is naturally captured by the existence of a temporal path where temporal edges can be traversed one after the other. When imposing constraints on how much time it is possible to wait at a node in-between two temporal edges, it then becomes interesting to consider temporal walks where it is allowed to visit several times the same node, possibly at different times. We study the complexity of computing minimum-cost temporal walks from a single source under waiting-time constraints in a temporal graph and ask under which conditions this problem can be solved in linear time. Our main result is a linear time algorithm when temporal edges have strictly positive travel times and when they are provided in input by non-decreasing departure time and also by non-decreasing arrival time. We use an algebraic framework for manipulating abstract costs enabling in particular the optimization of a large variety of combinations of criteria. It allows to improve previous results for several criteria such as number of edges or overall waiting time. This result is somehow optimal in several ways: a logarithmic factor in the time complexity appears to be necessary if the input contains only one ordering of the temporal edges (either by arrival times or departure times), or when temporal edges can have zero travel time.
-
10h00 - (LaBRI)
Simple, strict, proper, happy: A study of reachability in temporal graphsDynamic networks are a complex topic. Not only do they inherit the complexity of static networks (as a particular case) while making obsolete many techniques for these networks; they also happen to be deeply sensitive to specific definitional subtleties, such as strictness (can several consecutive edges be used at the same time instant?), properness (can adjacent edges be present at the same time?) and simpleness (can an edge be present more than once?). These features, it turns out, have a significant impact on the answers to various questions, which is a frequent source of confusion and incomparability among results. In this paper, we explore the impact of these notions, and of their interactions, in a systematic way. Our conclusions show that these aspects really matter. In particular, most of the combinations of the above properties lead to distinct levels of expressivity of a temporal graph in terms of reachability. Then, we advocate the study of an extremely simple model -- happy graphs -- where all these distinctions vanish. Happy graphs suffer from a loss of expressivity; yet, we show that they remain expressive enough to capture (and strengthen) interesting features of general temporal graphs. A number of questions are proposed to motivate the study of these objects further.
- 10h30 - Pause café
-
11h00 - (LaBRI)
Each participant can present open questions
- 12h30 - Déjeuner
- 14h - Départ
Participants :
- Stefan BALEV
- Vincent BRIDONNEAU
- Filippo BRUNELLI
- Arnaud CASTEIGTS
- Timothée CORSINI
- Monica CSIKOS
- Cyril GAVOILLE
- Frédéric GUINAND
- Michel HABIB
- Nicolas HANUSSE
- David ILCINKAS
- Colette JOHNEN
- Ralf KLASING
- Fabien de MONTGOLFIER
- Minh Hang NGUYEN
- Yoann PIGNÉ
- Mikaël RABIE
- Eric SANLAVILLE
- Jason SCHOETERS
- Mathilde VERNET
- Laurent VIENNOT
Transports en commun (merci Eric) :
Apparemment il y a un bus qui va de la gare de Poitiers à Chasseneuil, en ~ 20mn. Bus num 1. Et toutes les 30 mn. Il y en a un à 20h04, ce qui nous va bien car on arrive à 19h45 gare de Poitiers. Encore mieux, il y a un train qui part à 20h01 qui arrive plus près et qui ne mets que 6mn. (c'est le dernier). On peut supposer qu'il y ait la même fréquence le vendredi pour le retour.