Des chercheurs du MIT créent KLOS

Un puissant algorithme de parcours de graphes non orientés

Qu’est ce qu’un graphe ? Des points et des lignes. En tout cas, c’est la réponse que donnerait n’importe quel profane s’il était mis en présence de cette structure simple, mais puissante, dont les applications tant en génétique qu’en informatique sont légions.

La méthode de compression des fichiers au format Zip créée par l’américain David Huffman en 1952 est une application de la théorie des graphes. On peut également citer l’algorithme de recherche du plus court chemin proposé par le néerlandais Edgser Dijkstra, algorithme très employé dans le domaine des réseaux informatiques, où son utilité permet aux routeurs de déterminer le plus court chemin que doit emprunter un paquet pour atteindre sa destination.

Les graphes sont omniprésents en informatique. Leur origine est associée aux travaux du mathématicien Leonhard Euler en 1736, mais ils sont cependant très discrets. Combien sont-ils au courant de leur existence, alors qu’ils sont quotidiennement employés ?

Il n’est donc pas surprenant que le tout nouvel algorithme des chercheurs du MIT n’attire lui non plus l’attention, autant que le ferait la sortie d’un tout nouveau smartphone comme l’iPhone 5s par exemple.

Les travaux des chercheurs du MIT ont en effet porté sur la création d’un nouvel algorithme de parcours de graphe, dont l’évolution est quasi linéaire. Ils l’ont sobrement baptisé « KLOS algorithm », en l’honneur des chercheurs qui lui ont donné naissance (Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et Aaron Sidford).

KLOS est présenté comme l’algorithme de parcours de graphe le plus abouti à l’heure actuelle. Il serait plus performant que les algorithmes de flot maximum (max flot) connus. KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.

Existe-t-il déjà des bibliothèques d’implémentation de KLOS ? Aucune à l’heure actuelle. Les développeurs sont appelés à être patients, car ça ne saurait tarder.

Source: Rapport de recherche PDF

Et vous ?

Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?