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

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.