CODEWITHSUNDEEP
algorithmmathgraphgraph-algorithmhamiltonian-cycle
maximcore
maximcore

Reputation: 23

How to find Hamiltonian Cycle in a graph using BFS? (the condition is that the graph is exactly hamiltonian)

I am trying to solve the Hamiltonian Cycle problem.

The condition of my task is:

The group consists of N people. In it, everyone has exactly N / 2 friends. Friendship is symmetrical (if A is friend B, then B is friend A). One person in the group has a book (his number X), which everyone would like to read and then discuss with some of the others.

It is necessary to determine the method of transferring the book, in which it would visit everyone exactly once, passing only from friend to friend, and finally return to its owner.

That is, it satisfies the condition of the Dirac's theorem.

On small graphs my solutions works properly, but on big graphs my solution gives time limit exception.

Is there any method how it can be solved faster than O(n!)?

Upvotes: 1

Views: 856

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58211

There is a polynomial-time algorithm to find hamiltonian cycles in graphs where every vertex degree is at least N/2.

It's described in "A Simple Extension of Dirac’s Theorem on Hamiltonicity" Yasemin Büyükçolak, Didem Gözüpek, Sibel Özkan, Mordechai Shalom.

Upvotes: 1

Related Questions