Ionona Ranaivoson (GREYC, Université de Caen)

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^3)\) 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.