Temporalité, géométrie, et algorithmes efficaces sur les graphes
Spatiotemporal networks (STN) are networks whose attributes change over time while respecting certain geometric properties. Designing algorithms for STNs lies at the intersection of graphs (N), string algorithms (T) and algebra (S).
This ``HDR, habilitation à diriger des recherches'' covers my works over the past 15 years, divided into three components (N) (T) (S). A common topic is about graph modules and twins which can be seen as duplicates in a graph, hence very apt for factorisation operations:
- (N) The first component deals with graphs: I will give a comparative overview of algorithmic aspects of graph decompositions defined by parameters inspired by modular decomposition: cliquewidth, bimodule-width, rankwidth and booleanwidth.
- (T) The second component explores the extension from graphs to temporal graphs: Though most temporal versions of polynomial problems lead to NP-hard cases (matching, connected components, spanning tree, ...), I will show polynomial results for computing the temporal versions of modules, notably by testing the negation of being a module instead.
- (S) The last component sets the perspective for future directions of research on algebraic aspects of graphs and temporal graphs: Two exploratory results will be presented, using Euclidean geometry for the first case and division ring algebra for the second one.
Phd defence : 11/09/2023
Jury members :
Thomas Erlebach, Durham University [rapporteur]Arnaud Casteigts, Université de Genève [rapporteur]
Reza Naserasr, CNRS, [rapporteur]
Olivier Bodini, Université Sorbonne Paris Nord
Roland Grappe, Université Paris Dauphine
Maria Potop-Butucaru, Sorbonne Université
Nicolas Trotignon, CNRS
Laurent Viennot, INRIA
Researcher with HDR