LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Jobs

 Thesis : Mettre de l'ordre dans les graphes pour passer à l’échelle

PhD school thesis
Les algorithmes de graphes utilisés dans de nombreux contextes font face à la taille grandissante des données sur lesquelles on souhaite les exécuter. Pour de nombreuses applications même des algorithmes quadratiques sont trop lents pour être utilisables dans des contextes réels et il est nécessaire de disposer d’algorithmes, exacts ou d’approximation, de complexité linéaire ou quasi-linéaire. Plusieurs résultats montrent qu’en triant les sommets d’un graphe en fonction d’une propriété donnée puis en traitant les sommets du graphe suivant cet ordre il est possible de rendre certains algorithmes plus efficaces. Le travail proposé consiste à étudier à la fois les ordres pertinents, les algorithmes qui peuvent en tirer parti et à en proposer de nouveaux. L’implémentation efficace des algorithmes sera également un aspect important de la thèse.

Mots clefs : Graphe de terrain, Algorithmique de graphe, Passage à l'échelle, Compression de graphe

Ce projet de recherche doctoral fait l’objet d’une demande de financement auprès de « Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE) », le candidat retenu par son porteur devra donc participer au concours correspondant (prévoir un dossier et une audition) en vue d’obtenir le financement effectif.

More details here

Contact :Lionel Tabourier

 Mentions légales
Site map |