HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle

K. R. Seeja

Journal of Optimization, 2018, vol. 2018, 1-10

Abstract:

Hamiltonian Cycle Problem is one of the most explored combinatorial problems. Being an NP-complete problem, heuristic approaches are found to be more powerful than exponential time exact algorithms. This paper presents an efficient hybrid heuristic that sits in between the complex reliable approaches and simple faster approaches. The proposed algorithm is a combination of greedy, rotational transformation and unreachable vertex heuristics that works in three phases. In the first phase, an initial path is created by using greedy depth first search. This initial path is then extended to a Hamiltonian path in second phase by using rotational transformation and greedy depth first search. Third phase converts the Hamiltonian path into a Hamiltonian cycle by using rotational transformation. The proposed approach could find Hamiltonian cycles from a set of hard graphs collected from the literature, all the Hamiltonian instances (1000 to 5000 vertices) given in TSPLIB, and some instances of FHCP Challenge Set. Moreover, the algorithm has O(n 3 ) worst case time complexity. The performance of the algorithm has been compared with the state-of-the-art algorithms and it was found that HybridHAM outperforms others in terms of running time.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/7179/2018/9328103.pdf (application/pdf)
http://downloads.hindawi.com/journals/7179/2018/9328103.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjopti:9328103

DOI: 10.1155/2018/9328103

Access Statistics for this article

More articles in Journal of Optimization from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().