The project SPAWN is a theoretical computer science project, whose objective is to design high-level performance algorithms dedicated to path and walks problems in graphs.
Such problems arise in many real-world applications, such as route planning, design of transportation lines, or VLSI design for integrated circuits. In the 60s, famous algorithms were proposed to compute shortest paths in graphs, such as Dijkstra or Bellman-Ford. Since, many generalizations and variants of this classical combinatorial problem have been explored. Our intention is not only to focus on the recent trends in this research area - mixing fine-grained complexity, structural graph theory and algorithmics - but also to unify several research axes which evolved quite separately for treating path questions. Nowadays, problems with much more constraints are treated since they represent complex real-world issues. At the same time, new algorithmic frameworks are used to approach path-like problems modeling dynamic navigation: we can cite online algorithmics, reconfiguration techniques, prediction-based algorithmics.
Regarding path-related problems on graphs with many constraints, our major objective is to assess for which kind of instances such problems become polynomial-time solvable : grids, planar graphs, sparse graphs... Furthermore, we will propose reconfiguration techniques for path problems in order to produce solutions improving slightly existing ones which are not optimal or feasible. Finally, we will develop algorithms for navigation problems with uncertain environments: the goal is to walk efficiently on the graph while some data of the input might be inaccurate.
Events
Malory MARIN will join us as a postdoc in LIG from September 2026
