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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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