4551
правка
Irina (обсуждение | вклад) м (→Ссылка на код) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 29: | Строка 29: | ||
== Основные результаты == | == Основные результаты == | ||
Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем | Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем выполнения известны для многих специальных классов графов – в частности, графов ограниченного рода, графов с ограниченной степенью, ограниченной древесной шириной и ограниченной кратностью собственного значения. Самый быстрый теоретический алгоритм для графов общего вида требует <math>exp(n^{1/2+o(1)}) \; </math> времени [1], однако нет сведений о его практичности. | ||
В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в статье [5]. Известно [7], что она имеет экспоненциальное время | В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в статье [5]. Известно [7], что она имеет экспоненциальное время выполнения в наихудшем случае, но на практике этот наихудший случай встречается редко. | ||
правка