stage M2 LIP6: Etude d’un algorithme paramétré pour l’optimisation de la numérotation topologique d’un graphe orienté sans circuit.

Les ordres partiels représentés par des graphes orientés sans circuit, interviennent dans de nombreux modèles associés à des problèmes réels : en ordonnancement, ils permettent de modéliser des contraintes de précédence. Pour des applications informatiques, ces ordres sont associés à des transferts de données. Plusieurs problèmes d'optimisation sont liés à une numérotation topologique efficace des sommets de ces graphes, "DAG Bandwidth", "DAG SUM-CUT", "DAG MAX-CUT" par exemple. Il s'agit dans ce stage de les aborder sous l'angle de la complexité paramétrée, en étudiant en particulier le paramètre défini par la k-dégénerescence du graphe de co-comparabilité de l'ordre partiel. Un algorithme FPT pour ce paramètre a en effet  été défini pour le problème "DAG SUM-CUT". Le but de ce stage est d’étudier si cet algorithme peut être étendu à d'autres critères d’optimisation, le cas échéant,  de programmer les algorithmes  et d’en étudier les performances en temps expérimentalement.

Le sujet complet peut être consulté ici.