Graphes Ordonnés, Décompositions, Algorithmes et Structures – GODASse

Stocker un graphe dans une machine (modèle de von Newmann) définit implicitement un ordre sur ses sommets. Nous observons que les algorithmes de graphes peuvent tirer parti d'une utilisation intelligente de ces ordres. On peut penser à l'algorithme (Kosaraju-Sahrir 1981) du calcul des composantes fortement connexes d'un graphe pour lequel une complexité linéaire peut être obtenues si les sommets sont ordonnés à l'aide d'un premier parcours en profondeur. Nous remarquons également que les ordres sur les sommets sont fréquemment utilisés pour caractériser des propriétés de graphes. Ces caractérisations sont basées sur l'exclusion de "motifs", qui sont des (petits) graphes dont les sommets sont ordonnés. Un exemple courant est le fait que le nombre chromatique d'un graphe est au plus k si et seulement si ses sommets peuvent être ordonnés de telle sorte que le chemin ordonné (d'une extrémité à l'autre) de longueur k est exclu.

Il est surprenant de constater que peu de choses sur les graphes ordonnés sont connues et qu'à ce jour, la théorie des graphes ordonnés, tant du point de vue combinatoire qu'algorithmique, n'a pas été étudiée de manière systématique. L'objectif de cette proposition est de combler cette lacune. Le projet sera organisé en trois groupes de travail :
WP1- Graphes ordonnés pour caractériser des certificats de propriétés des graphes
WP2 - Aspects théoriques et algorithmiques des graphes ordonnés
WP3 - Extensions des graphes ordonnés
Nous visons à prouver des résultats combinatoires sur les graphes ordonnés et à développer des méthodes de décomposition dédiées qui serviront de base à la conception d'algorithmes efficaces pour les graphes (ordonnés).