1
$\begingroup$

I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher success probability.

I also read the question Efficient Hamiltonian cycle algorithms for graph classes.

But it does answer my concern.

$\endgroup$
  • 1
    $\begingroup$ You will need to be more specific for a helpful answer. Here is a list of resources you might want to consult: web.archive.org/web/20100324030526/http://alife.ccp14.ac.uk/… $\endgroup$ – Carlo Beenakker Apr 12 '19 at 12:19
  • $\begingroup$ Thanks a lot! But I cannot open this link after some times trying ... Is this link correct? Thanks again! $\endgroup$ – Licheng Wang Apr 12 '19 at 12:37
  • $\begingroup$ it works for me... $\endgroup$ – Carlo Beenakker Apr 12 '19 at 12:49
  • 2
    $\begingroup$ Does "needless a circle" mean that the Hamiltonian path need not be a cycle? If so, probably "not necessarily" is clearer than "needless". $\endgroup$ – LSpice Apr 12 '19 at 14:57
  • $\begingroup$ Yes! Thanks! I have edited the title just now. $\endgroup$ – Licheng Wang Apr 13 '19 at 1:11
1
$\begingroup$

The Hamiltonian path problem is NP-complete in general, so only heuristics could exist if P≠NP.

The rotation-extension heuristic may be the simplest heuristic:

Input: undirected graph G with size n
Let P be a path
Let e be a random edge of G
P:=[e]
Loop:
    If Extension(G,P)≠∅:
        P:=Extension(G,P)
        Goto Loop
    Let Π be the family of the Posa extensions¹ of P in G
        For π in Π:
            If Extension(G,π)≠∅:
                P:=Extension(G,π)
                Goto Loop
    {Remark: The heuristic is not able to extend the path, so we must stop}
     If P is a hamiltonian path, return P, otherwise stop without returning anything.

Subprocedure: Extension
Input: undirected graph G and a path P⊆G
    For x in vertices of G:
        if x is connected with one of P's endpoints p:
            Return P+(p,x)
    Return ∅

1: as defined in https://www.sciencedirect.com/science/article/pii/S0012365X06005097

In other words, the program finds extensions and extensions after rotations until there're none, and return a hamiltonian path if there is one.

For more sophiscated heuristics, one can use methods from the Flinders Hamiltonian Cycle Project.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.