DATA: Mar 31/01/2023
ORE: 14:30
LUOGO: Sala del Consiglio (VIII piano), via Celoria 18

SPEAKER: Fabrice Lécuyer (Sorbonne Université + LIP6, Paris)

RESPONSIBLE: Paolo Boldi

ABSTRACT

Networks can represent a variety of real-life situations (hyperlinks on the internet, trade, scientific citations...) and their ever-increasing size requires fast and scalable graph algorithms. A crucial technique consists in ordering the nodes of a graph according to some properties, such as their degree or centrality. This technique is used in state-of-the-art methods for various graph problems, among which cache optimisation, compression and pattern mining.
We present two contributions based on this method. First, we analyse the precise complexity of a triangle listing algorithm and we infer new orderings that reduce it and accelerate the listing. Second, we show how an approximation algorithm or vertex cover can leverage two distinct orderings to give better guarantees without losing on scalability.