Какой на данный момент самый быстрый алгоритм поиска гамильтонова цикла в небольшом графе (~ 50-70 вершин)?
1 ответ
Всё зависит от ваших требований: к примеру, имеет ли ваш граф какие-то структурные особенности, готовы ли вы работать с рандомизированным алгоритмом (т.е., алгоритмом, который с небольшой вероятностью может дать неправильный ответ) и т.д. Не претендуя на полный обзор литературы по теме, упомяну несколько известных результатов. Я не знаю, есть ли у вас доступ к журналам, если нет - дайте мейл и я всё вышлю.
- Если ваш граф планарный и 4-связный, то задача решается за линейное время (Чиба, Нишизеки 1989), а если просто планарный то за О(c^\sqrt(n)), где константа c не зависит от графа (Дейнеко, Клинц, Вугингер 2006)
- Если ваш граф т.н. cocomparability graph (интересно, как это по-русски?), то задача полиномиальна (Деогун, Штейнер 1994)
- Если вы готовы работать с рандомизированным алгоритмом, то O(1.657^n); для двудольных графов O(1.414^n) (Бьёрклунд 2010)
- Если степень вершин не превышает 3, то задача всё равно в NP, а лучший алгоритм - O(1.251^n) (Ивама, Накашима 2007)
-
2