HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle
Author
Source
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-10-16
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
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(n3) 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.
American Psychological Association (APA)
Seeja, K. R.. 2018. HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle. Journal of Optimization،Vol. 2018, no. 2018, pp.1-10.
https://search.emarefa.net/detail/BIM-1197290
Modern Language Association (MLA)
Seeja, K. R.. HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle. Journal of Optimization No. 2018 (2018), pp.1-10.
https://search.emarefa.net/detail/BIM-1197290
American Medical Association (AMA)
Seeja, K. R.. HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle. Journal of Optimization. 2018. Vol. 2018, no. 2018, pp.1-10.
https://search.emarefa.net/detail/BIM-1197290
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1197290