Etude structurelle et algorithmique des graphes pouvant être séparés avec des plus courts chemins

Abstract

Les graphes sont des objets couramment utilisés pour modéliser de nombreuses situations réelles comme des réseaux routiers, informatiques ou encore électriques. Ils permettent de résoudre des problèmes sur ces réseaux comme le routage (aller d'un sommet à un autre en suivant les arêtes du graphe) ou encore leur exploration (obtenir une carte du graphe étudié). Les réseaux étudiés, et donc les graphes qui les modélisent, peuvent être grands, c'est-à-dire avoir un très grand nombre de sommets. Dans ce cas, comme dans le cas de l'étude de grandes données en général, nous pouvons utiliser le paradigme << Diviser pour mieux régner >> pour répondre aux questions posées. En effet, en travaillant sur des petites parties du graphe et en fusionnant les résultats obtenus sur ces petites parties, on peut obtenir le résultat sur le graphe global. Dans ce document, nous présenterons une manière de décomposer les graphes en utilisant des plus courts chemins comme séparateurs. Cette décomposition permet d'obtenir, par exemple, un routage efficace, un étiquetage compacte pour pouvoir estimer les distances entre les sommets d'un graphe ou encore une navigation efficace dans les graphes<< petit monde >>. Cette méthode va nous permettre de définir de nouvelles classes de graphes.