Contra-exemplo para o algoritmo eficiente de Corneil para isomorfismo gráfico

16

No artigo Um Algoritmo Eficiente para Isomorfismo de Gráfico de Corneil e Gotlieb, 1970, foi declarada uma conjectura sobre a qual o algoritmo declarado se baseava na resolução de IG em tempo polinomial. Nomeadamente:

que os gráficos representativos exibem a partição de automorfismo do gráfico fornecido

Obviamente, essa conjectura não está comprovada até agora (caso contrário, saberíamos que o IG está em P). Minha pergunta é se ela já foi mostrada como falsa e, possivelmente, um exemplo contrário foi dado?

John D.
fonte

Respostas:

18

Mathon mostrou que a conjectura usada por Corneil e Gotlieb é falsa. A primeira referência afirma esse fato.

1- P. Foggia, C. Sansone, M. Vento, Uma Comparação de Desempenho de Cinco Algoritmos para Isomorfismo de Gráfico, Proc. 3º Workshop IAPR-TC15 Representações baseadas em gráficos no reconhecimento de padrões, 2001, pp. 188-199.

2- R. Mathon, Gráficos de amostra para teste de isomorfismo, Congressus Numerantium, 21, pp. 499-517, 1978

Mohammad Al-Turkistany
fonte