The proposed heuristic is a combination of greedy depth first search, unreachable vertex, and rotational transformation heuristics.

Rotational Transformation. Rotational transformation [11] and its variations are found to be powerful heuristics for finding Hamiltonian cycle.

The procedure of rotational transformation is summarized below.

In the proposed algorithm, rotational transformation is used for two purposes.

In the first case highest degree end of the path is selected for rotational transformation since it increases the probability of getting a new end.

If the initial path created is not Hamiltonian (less number of vertices than the total number of vertices), then select the highest degree end of the initial path for rotational transformation. This is to increase the probability for getting a new end vertex for extending the path further to create a Hamiltonian path.

Otherwise, apply rotational transformation to the smallest degree vertex repeatedly until getting a new end vertex which can be connected to the other end vertex to form the Hamiltonian cycle.