3

I am trying to solve the Hamiltonian Cycle problem. I am able to find a path with all the vertices, but unable to complete the cycle.

Can someone provide me with an algorithm to find the cycle?

Improve this question

4 Answers 4

Reset to default
17

Determining if a graph has a Hamiltonian Cycle is a NP-complete problem. This means that we can check if a given path is a Hamiltonian cycle in polynomial time, but we don't know any polynomial time algorithms capable of finding it.

The only algorithms that can be used to find a Hamiltonian cycle are exponential time algorithms. Some of them are

  • Brute force search
  • Dynamic programming
  • Other exponential but nevertheless faster algorithms that you can find here
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

This is one of the most basic problems in computer science, there are plenty solutions depending on what you want: start here http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms

There are also SO answers related: here and here

Improve this answer

Comments

1

I hope this below link which i found will help you lot with clear explanation...... http://www.geeksforgeeks.org/archives/19092

Improve this answer

Comments

0

Use a SAT solver if possible. They don't have the good theoretical time limits of the algorithms in the Wikipedia article, but in practice they can often solve them surprisingly quickly.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.