Temporal graphs provide a useful model for many real-world networks. Unfortunately the majority of algorithmic problems we might consider on such graphs are intractable. There has been recent progress in defining structural parameters which describe tractable cases by simultaneously restricting the underlying structure and the times at which edges ...
The Hydro Unit Commitment problem (HUC) is a difficult problem playing a major role in the scheduling of daily electricity production at EDF. In this thesis, we study different models and algorithms to solve the special case of the single-unit HUC problem (1-HUC). Studying this case is relevant for the following reasons. On the one hand, there are ...
A resolving set R in a graph G is a set of vertices such that every vertex of G is uniquely identified by its distances to the vertices of R. Introduced in the 1970s, this concept has been since then extensively studied from both combinatorial and algorithmic point of view. We propose a generalization of the concept of resolving sets to temporal gr...
For an undirected unweighted graph G = (V,E) with n vertices and m edges, let d(u,v) denote the distance from u ∈ V to v ∈ V in G. An (α,β)-stretch approximate distance oracle (ADO) for G is a data structure that given u,v ∈ V returns in constant (or near constant) time a value dˆ(u,v) such that d(u,v) ≤ dˆ(u,v) ≤ α⋅ d(u,v) + β, for some reals α > ...
Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as "interval thinness" and...
Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear system solvers are crucial algorithmic primitives to fast computation of fundamental problems on random walks, such as computing stationary distributions, hitting and commu...
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) ti...
Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n^{1.9}) worst-case runtime, even when the input graph has n² edges? I...
We explore the 4-coloring problem, a fundamental combinatorial NP-hard problem. Given a graph G, the 4-coloring problem asks whether there exists a function f from the vertex set of G to {1,2,3,4} such that f(u)≠ f(v) for each edge uv of G. Such function f is referred to as a 4-coloring of G. The fastest known algorithm for the 4-coloring problem, ...
Les rotors sont des orientations du voisinage des sommets d'un graphe qui permettent de l'explorer de façon déterministe, mais complexe, à l'aide de règles simples : les marches de rotors. Leur étude connaît un essor important dans la communauté informatique depuis une dizaine d'années. Ces processus déterministes sont très prometteurs pour progres...
