Sur le graphique Isomorphism Complete Problems

Je suis intéressé à étudier les problèmes complets de l'isomorphisme graphique (GI).

Dans le document "Problems Polynomially Equivalent to Graph Isomorphism" de Kellogg S. Booth, (1979), a prouvé que de nombreux problèmes de base sont GI complets en utilisant des techniques de remplacement des bords, des techniques de composition, etc.

Je voudrais en savoir plus sur les techniques utilisées dans les articles récents.

Quelqu'un peut-il me suggérer des articles récents qui sont plus concentrés à prouver qu'une classe graphique est GI complète.

cc.complexity-theory reference-request graph-isomorphism Kumar
la source

voir aussi wikipedia isomorphisme graphique complet et problèmes gastro-intestinaux

vzn

Qu'avez-vous fait pour essayer de trouver de tels papiers par vous-même? Avez-vous essayé d'utiliser des méthodes standard de recherche documentaire (par exemple, en recherchant sur Google Scholar, en trouvant tous les articles qui citent l'article Booth, etc.)?

Réponses:

Complétude de l'isomorphisme des graphes pour les graphes parfaits et les sous-classes de graphes parfaits C. Boucher D. Loker (2006)

Dans cet article, nous prouvons que l'isomorphisme décisif des graphes à double division, la classe de graphes présentant une jointure 2 et la classe de graphes présentant une partition asymétrique équilibrée sont GI-complets. De plus, nous montrons que le problème de l'IG pour la plus grande classe incluant ces classes de graphes - c'est-à-dire la classe des graphes parfaits - est également GI-complet.

vzn
la source

@gold great; cela m'a sauté aux yeux parmi les différentes alternatives, en partie parce que les graphiques parfaits semblent avoir de nombreuses connexions profondes avec la théorie de la complexité et semblent avoir peut-être d'autres liens importants non encore découverts mais "à l'horizon".

vzn