Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Could you name any of the smart algorithms for the Hamiltonian Path problem? – A.Schulz Nov 30 '12 at 13:02
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 ;-) – Hebi Nov 30 '12 at 16:03
Seems to me that you can blow up the graph by a factor of $n$, direct it, and then search for directed $n$-cycles. – Raphael Jul 5 at 8:51
See also the comments in – D.W. Jul 5 at 15:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.