Какие алгоритмы применяются для поиска гамильтонова пути в неориентированных графах?

Для поиска гамильтонова пути в неориентированных графах применяют, например, следующие алгоритмы:

• Наивная реализация. acm.math.spbu.ru Самый простой подход — сгенерировать все возможные перестановки из N вершин (их количество равняется N!). acm.math.spbu.ru Для каждой перестановки исследовать, является ли она правильным гамильтоновым путём, проверяя, есть ли ребро между соседними вершинами или нет. acm.math.spbu.ru
• Алгоритм перебора с возвратом. spravochnick.ru К уже выстроенному отрезку маршрута прибавляются лишь те вершины, которые соединяются ребром с конечной вершиной маршрута и не посещались раньше. spravochnick.ru После прибавления новой вершины к путевому маршруту делается рекурсия, то есть запуск алгоритма из новой вершины. spravochnick.ru
• Алгоритм динамического программирования. ru.wikipedia.org neerc.ifmo.ru В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. ru.wikipedia.org
• Процедура поиска Франка Рубина. ru.wikipedia.org Рёбра графа разбиваются на три класса — те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. ru.wikipedia.org В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. ru.wikipedia.org