1

Какой на данный момент самый быстрый алгоритм поиска гамильтонова цикла в небольшом графе (~ 50-70 вершин)?

1 ответ 1

3

Всё зависит от ваших требований: к примеру, имеет ли ваш граф какие-то структурные особенности, готовы ли вы работать с рандомизированным алгоритмом (т.е., алгоритмом, который с небольшой вероятностью может дать неправильный ответ) и т.д. Не претендуя на полный обзор литературы по теме, упомяну несколько известных результатов. Я не знаю, есть ли у вас доступ к журналам, если нет - дайте мейл и я всё вышлю.

  • Если ваш граф планарный и 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)
1
  • 2
    Ого, вот это теоретическая подготовка!
    – VladD
    30 окт 2013 в 23:35

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.