~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ /* THIS FILE WAS GENERATED */ /* EDIT THE FILE "indexheader" INSTEAD */ /* OR ACCESS THE DATABASE */ {{page>.:indexheader}} \\ ==== Prochaines séances ==== [[seminaires:adg:index|Algorithmique distribuée et graphes]]\\ Mardi 30 avril 2024, 15 heures 15, 3052 Sophie Germain\\ **Gianlorenzo D'Angelo** (GSSI) //Sparse Temporal Spanners with Low Stretch// \\ A temporal graph is an undirected graph G = (V,E) along with a function that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum number of edges of a temporal path from u to v. A temporal alfa-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V, up to a multiplicative stretch factor of alfa. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k-1)-spanner with \tilde{O}(kn^{1+1/k}) edges, where k > 1 is an integer parameter of choice and n is the number of nodes in G. Choosing k = log n, we obtain a temporal O(log n)-spanner with \tilde{O}(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] to preserve temporal connectivity. We then turn our attention to general temporal graphs. Since \Omega(n^2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that \tilde{O}(n/log(1+epsilon)) edges suffice to obtain a stretch of (1+epsilon), for any small epsilon > 0. This result is essentially tight in the following sense: there are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use \Omega(n^2) edges. [[seminaires:adg:index|Algorithmique distribuée et graphes]]\\ Mardi 30 avril 2024, 11 heures, 1003 Sophie Germain\\ **Alexis Baudin** (LIP6) //Faster maximal clique enumeration in large real-world link streams// \\ Link streams offer a good model for representing interactions over time. They consist of links (b,e,u,v), where u and v are vertices interacting during the whole time interval [b,e]. In this talk, we deal with the problem of enumerating maximal cliques in link streams. A clique is a pair (C,[t0,t1]), where C is a set of vertices that all interact pairwise during the full interval [t0,t1]. It is maximal when neither its set of vertices nor its time interval can be increased. Some of the main works solving this problem are based on the famous Bron-Kerbosch algorithm for enumerating maximal cliques in graphs. We take this idea as a starting point to propose a new algorithm which matches the cliques of the instantaneous graphs formed by links existing at a given time to the maximal cliques of the link stream. We compute its complexity, which is better than the state-of-the art ones in many cases of interest. We also study the output-sensitive complexity, which is close to the output size, thereby showing that our algorithm is efficient. To confirm this, we perform experiments on link streams used in the state of the art, and on massive link streams, up to 100 million links. In all cases our algorithm is faster, mostly by a factor of at least 10 and up to a factor of 10^4. Moreover, it scales to massive link streams for which the existing algorithms are not able to provide the solution. For more details, please consult the following paper: https://arxiv.org/abs/2302.00360. \\ ==== Séances passées ==== \\ === Année 2024 === {{page>.:adg2024}} \\ === Année 2023 === {{page>.:adg2023}} \\ === Année 2022 === {{page>.:adg2022}} \\ === Année 2021 === {{page>.:adg2021}} \\ === Année 2020 === {{page>.:adg2020}} \\ === Année 2019 === {{page>.:adg2019}} \\ === Année 2018 === {{page>.:adg2018}} \\ === Année 2017 === {{page>.:adg2017}} \\ === Année 2016 === {{page>.:adg2016}}