Количество гамильтоновых путей в графах
Я пытаюсь найти быстрый алгоритм, который может вычислить количество гамильтоновых путей в неориентированном графе. Я видел это в сети, но похоже, что все гамильтоновы пути начинаются с одной конкретной вершины. (например, вершина 0 в этом коде)
Одна из идей состоит в том, чтобы запустить описанный выше алгоритм для всех вершин в качестве отправной точки, а затем для получения ответа половину общего числа путей (поскольку каждый путь имеет 2 начальные вершины, и при таком подходе мы вычисляем каждый путь дважды). Мне было интересно, есть ли прямой алгоритм с возвратом, который быстрее, чем то, что я только что упомянул выше.
Кроме того, если m - количество ребер в нашем графе, для простоты предположим, что m <= 1/2 C(n,2)