Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that.
Now let's make things interesting: sometimes, when I arrive at a vertex, the edges connected to that vertex change. I.e. some will be removed, others appear. It is only depending on the edge I used before which egdes will change.
That means, if I go from vertex $v_1$ to $v_x$, edges connected to $v_x$ will change in the way $b_{1,x}$. if I arrived $v_x$ via $v_2$, edges will change in the way $b_{2,x}$ and so on.

I am looking for a efficient algorithm telling me if there is a hamiltonian path and output that if so. Has anybody ideas on how to approach that? Or has anyone an idea if this can be transformed into another better known problem?

  • 4
    $\begingroup$ Could you name any of the smart algorithms for the Hamiltonian Path problem? $\endgroup$ – A.Schulz Nov 30 '12 at 13:02
  • 1
    $\begingroup$ This page presents some good heuristics. Particularly, I waas pretty impressed by their snakes-and-ladders heuristic, which you can try out via an applet. But don't attach too much importance to that sentence. It's not the point here ;-) $\endgroup$ – Hebi Nov 30 '12 at 16:03
  • $\begingroup$ Seems to me that you can blow up the graph by a factor of $n$, direct it, and then search for directed $n$-cycles. $\endgroup$ – Raphael Jul 5 '16 at 8:51
  • $\begingroup$ See also the comments in cs.stackexchange.com/q/10482/755 $\endgroup$ – D.W. Jul 5 '16 at 15:04

Your Answer

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

Browse other questions tagged or ask your own question.