- Computer Science Laboratory

LÉCUYER Fabrice

PhD Student at Sorbonne University
Team : ComplexNetworks
https://fabrice.lecuyer.me
https://fabrice.lecuyer.me

Supervision : Lionel TABOURIER
Co-supervision : Clémence Magnien

Ordering nodes to scale to large real-world networks

Networks are prevalent in various real-world situations such as the internet, trade, and scientific citations. As these networks grow larger, fast and scalable graph algorithms are needed to handle them. One key technique for achieving this is node ordering, where nodes are arranged based on certain properties like degree or centrality.

This approach has been adopted by state-of-the-art methods for a range of graph problems including cache optimisation, compression, and pattern mining.

This thesis presents novel contributions that leverage node ordering. First, we analyse the complexity of a triangle listing algorithm and propose new node orderings that reduce it and accelerate the listing process. Second, we show how simple orderings can improve guarantees for vertex cover without compromising scalability.


Phd defence : 07/06/2023

Jury members :

Laurent Viennot, Directeur de recherches INRIA, IRIF Paris Cité [Rapporteur]
Marco Bressan, Maître de conférences, Université de Milan [Rapporteur]
Claire Hanen, Professeure des universités, LIP6
David Coudert, Directeur de recherches INRIA, Sophia
Rémy Cazabet, Maître de conférences, LIRIS, Lyon 1
Clémence Magnien, Directrice de recherches CNRS, LIP6
Lionel Tabourier, Maître de conférences, LIP6

Departure date : 08/31/2023

2021-2024 Publications