CE23 - Intelligence artificielle

Linear Algorithms for Massive Real-World Graphs – LiMass

Submission summary

Web search, drug design and traffic management are only a few examples of crucial applications that nowadays rely on the analysis of graphs. Involved graphs have become increasingly massive sometimes reaching trillions of edges such as the Web graph, Facebook, Internet or a human brain. Only quasi-linear time algorithms can process these massive graphs in a reasonable amount of time on the best supercomputers.

On the one hand, many important problems seem to require more than quadratic time to solve them in the worst case. On the other hand, it has been observed that many algorithms are much more efficient on real-world graphs than in such a worst case scenario. We suggest focussing on graph instances encountered in practice and design quasi-linear time algorithms for such real-world graphs by identifying, formalizing and leveraging their structural properties.

Project coordinator

Monsieur Lionel Tabourier (Laboratoire d'informatique de Paris 6)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LIP6 Laboratoire d'informatique de Paris 6

Help of the ANR 194,400 euros
Beginning and duration of the scientific project: March 2020 - 42 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter