Parameterized optimization: going beyond treewidth?
Vendredi 14 juin 2013, 14h, en salle 201, Binh Minh Bui Xuan, chargé de recherche au LIP6 (joint work with J.-F. Raymond and P. Trebuchet)
A major trend in parameterized algorithms aims at solving NP-hard graph problems in two steps: (1) recursively divide the input graph into chunks not increasing the value of a certain "width" parameter; (2) solve the NP-hard problem at hand along the chunk divisions. The two stage divide-and-conquer paradigm is commonly addressed as (1) finding good heuristics/approximation for the width parameter; (2) dynamic programming solving the NP-hard problem at hand .

(Modélisation, Information & Systèmes) fédère des enseignants-chercheurs de l’UPJV en Informatique, Automatique, Robotique et Vision par ordinateur. Les objectifs scientifiques du laboratoire s’inscrivent dans les thématiques des Sciences et techniques de l’information et de la communication (STIC). Les travaux de recherche qui y sont développés trouvent de nombreuses applications : Véhicule, Cybersécurité, Énergie, Robotique, Musique, Patrimoine, Santé...