Sobre los problemas completos del isomorfismo gráfico

11

Estoy interesado en estudiar los problemas completos del isomorfismo gráfico (IG).

En el documento "Problemas polinomialmente equivalentes al isomorfismo gráfico" de Kellogg S. Booth, (1979), demostró que muchos problemas básicos se completan GI mediante el uso de técnicas de reemplazo de bordes, técnicas de composición, etc.

Me gustaría aprender algunas técnicas más que se utilizan en artículos recientes.

¿Puede alguien sugerirme algunos documentos recientes que están más concentrados en probar que alguna clase de gráfico es IG completa?

cc.complexity-theory reference-request graph-isomorphism Kumar
fuente
44
vea también isomorfismo gráfico de
vzn
2
¿Qué has hecho para tratar de encontrar esos documentos por tu cuenta? ¿Has intentado usar métodos de búsqueda de literatura estándar (por ejemplo, buscar en Google Scholar, encontrar todos los documentos que citan el papel de Booth, etc.)?
DW

Respuestas:

4

En este artículo, demostramos que decidir el isomorfismo de los gráficos de doble división, la clase de gráficos que exhiben una unión de 2 y la clase de gráficos que exhiben una partición asimétrica equilibrada son GI completos. Además, mostramos que el problema de GI para la clase más grande, incluidas estas clases de gráficos, es decir, la clase de gráficos perfectos, también es GI completo.

vzn
fuente
@ dorado genial; me llamó la atención entre las diversas alternativas, en parte porque los gráficos perfectos parecen tener muchas conexiones profundas con la teoría de la complejidad y posiblemente tienen algunos lazos más grandes aún no descubiertos pero "en el horizonte".
vzn