CE23 - Intelligence artificielle

Algorithmes linéaires pour les graphes de terrain massifs – LiMass

Résumé de soumission

Les moteurs de recherche, la conception de médicament et la gestion du trafique ne sont que quelques exemples d’applications qui
reposent sur l'analyse de graphe. Les graphes concernés sont de plus en plus massifs, atteignant parfois plusieurs trillions de liens.
Seuls des algorithmes de complexité quasi-linéaire peuvent traiter de tels graphes en un temps raisonnable sur les meilleurs
superordinateurs.
Concevoir des algorithmes quasi-linéaire pour toutes les instances possibles (c'est-à-dire dans le pire cas) pour résoudre des
problèmes fondamentaux (tels que trouver une clique maximum, trouver une coupe maximum ou lister tous les k-motifs) semble
impossible. Cependant, beaucoup d'algorithmes sont beaucoup plus efficaces sur des graphes de terrain (graphes rencontrés en
pratique) que dans le pire cas. Nous suggérons donc de concevoir des algorithmes quasi-linéaire sur les graphes de terrain en
identifiant, formalisant et tirant parti de leurs propriétés structurelles.

Coordinateur du projet

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

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIP6 Laboratoire d'informatique de Paris 6

Aide de l'ANR 194 400 euros
Début et durée du projet scientifique : mars 2020 - 42 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter