Séminaire ALGO : Ionona Ranaivoson (GREYC) « Isomorphisme de sous-graphes (SubIso) des graphes séries-parallèles (SP-graphes) et couvertures par trous »

On s’intéresse au problème SubIso: étant donnés deux graphes non orientés G et H, déterminer si G contient un sous-graphe qui est isomorphe à H. Le problème SubIso est NP-complet en général. Mais des algorithmes polynomiaux de SubIso existent pour les graphes extra-planaires biconnexes (en O(n³) par [Lingas86]) et pour les SP-graphes biconnexes (en O(n^6.5) par [Lingas-Syslo 88]).

Nous revisiterons ces algorithmes à l’aide des couvertures par trous des SP-graphes, que nous savons être acycliques. En particulier, ces problèmes modélisent différents types d’applications en chimie et biologie, où on manipule différents objets représentés par des graphes extra-planaires, etc.