Контрпример для эффективного алгоритма Корнеила для графа Изоморфизм

16

В работе «Эффективный алгоритм изоморфизма графов » Корнейла и Готлиба, 1970 г. была высказана гипотеза, на которой основывался алгоритм для решения GI за полиномиальное время. А именно:

что репрезентативные графы демонстрируют автоморфизм разбиения данного графа

Очевидно, что эта гипотеза не доказана до сих пор (иначе мы бы знали, что GI находится в P). Мой вопрос заключается в том, было ли это доказано, что оно было ложным, и, возможно, был дан контрпример?

Джон Д.
источник

Ответы:

18

Матон показал, что гипотеза Корнейла и Готлиба неверна. Первая ссылка утверждает этот факт.

1- P. Foggia, C.Sansone, M. Vento, Сравнение производительности пяти алгоритмов изоморфизма графов, Proc. 3-й семинар IAPR-TC15 Представления на основе графов в распознавании образов, 2001, с. 188-199.

2- Р. Матон, Примеры графиков для проверки изоморфизма, Конгресс Numerantium, 21, с. 499-517, 1978

Мухаммед Аль-Туркистани
источник