Macé de Gastines, Etienne
[Verfasser:in]
;
Normandie
[Mitwirkende:r];
Portier, Bruno
[Mitwirkende:r]
Modélisation, approche polyédrale et approche arborescente pour des problèmes de comparaison de graphes ; Modeling, polyhedral approach and tree search for graph matching problems
Titel:
Modélisation, approche polyédrale et approche arborescente pour des problèmes de comparaison de graphes ; Modeling, polyhedral approach and tree search for graph matching problems
Beteiligte:
Macé de Gastines, Etienne
[Verfasser:in]
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Le problème de comparaison de graphes (graph matching en anglais) est une branche de la théorie des graphes qui vise à étudier la ressemblance structurelle entre des graphes. Ce domaine possède de nombreuses applications dans les domaines de la visualisation informatique, de l’analyse de données et de la biologie. Les problèmes en jeu sont intrinsèquement difficiles et leur résolution exacte a été l’objet de recherches approfondies, notamment via les techniques de recherche arborescente et de programmation par contraintes. En revanche, l’approche polyédrale n’a reçu qu’un intérêt limité dans ce domaine, et il est intéressant d’étudier l’apport des techniques de programmation linéaire en nombres entiers sur ce type de problèmes. Nous présentons dans un premier chapitre le domaine de la comparaison de graphes, en introduisant les domaines d’applications principaux, en définissant formellement les principales variantes de problèmes de comparaison de graphes et en rappelant les principaux résultats théoriques qui s’y rattachent et les relient. Nous présentons ensuite un état de l’art des techniques exactes utilisées pour résoudre ces problèmes, et présentons les différents outils pour les résoudre de manière approchée. Dans le second chapitre, nous nous intéressons au problème d’isomorphisme de sous-graphes non induit. Nous y présentons les principaux résultats polyédraux obtenus sur le sujet, et nous introduisons de nouvelles formulations linéaires en nombres entiers modélisant le problème. Nous comparons ces formulations entre elles, tant du point de vue théorique que du point de vue numérique. Nous présentons certaines familles de coupes. Nous comparons aussi les performances de l’approche polyédrale avec le solveur Glasgow, basé sur la programmation par contraintes. Les résultats mettent en avant que la programmation par contraintes s’avère la plus efficace, mais qu’il reste des pistes d’exploration pour l’approche polyédrale. Constatant que l’approche polyédrale serait sans doute un meilleur choix sur des ...