А интересует теория или практика по данному вопросу? Если теория, то ситуация такова.
Полиномиальных алгоритмов не известно. Однако не известно принадлежит ли эта задача NPC. Лучший точный алгоритм работает за e^{\sqrt{n * log(n)}}, и он довольно сложен.
Существующие алгоритмы: 1. O(n^2) работает для почти всех графов (он детерминированный, ошибка на некоторых входах). 2. e^{\sqrt{n * log(n)}} кто автор точно не помню, идея основана на алгоритме Симса для изоморфизма групп. 3. Алгоритм ВейсфейлераЛемана, есть экспоненциальная нижняя оценка, но на практике работает не плохо.
//logic.pdmi.ras.ru/csclub/courses/ Собственно здесь есть все, что я перечислил. В том числе и ссылки на некоторые практические алгоритмы.
а тупо поиск с возвратом не подойдет? аля перебираем подстановки, и если какаято часть подстановки не подходит, то не проверяем все подстановки с данной частью.
А интересует теория или практика по данному вопросу? Если теория, то ситуация такова.
Полиномиальных алгоритмов не известно. Однако не известно принадлежит ли эта задача NPC. Лучший точный алгоритм работает за e^{\sqrt{n * log(n)}}, и он довольно сложен.
Существующие алгоритмы:
1. O(n^2) работает для почти всех графов (он детерминированный, ошибка на некоторых входах).
2. e^{\sqrt{n * log(n)}} кто автор точно не помню, идея основана на алгоритме Симса для изоморфизма групп.
3. Алгоритм ВейсфейлераЛемана, есть экспоненциальная нижняя оценка, но на практике работает не плохо.
//logic.pdmi.ras.ru/csclub/courses/
Собственно здесь есть все, что я перечислил. В том числе и ссылки на некоторые практические алгоритмы.
Оу, спасибо огромное бро! Не ожидал такого удовольствия!
а тупо поиск с возвратом не подойдет?
аля перебираем подстановки, и если какаято часть подстановки не подходит, то не проверяем все подстановки с данной частью.
можно конечно, только работать скорее всего будет не очень быстро.
Например на регулярных графах.
не за что.