HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle
المؤلف
المصدر
العدد
المجلد 2018، العدد 2018 (31 ديسمبر/كانون الأول 2018)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2018-10-16
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص 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.
نمط استشهاد جمعية علماء النفس الأمريكية (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
نمط استشهاد الجمعية الأمريكية للغات الحديثة (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
نمط استشهاد الجمعية الطبية الأمريكية (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
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1197290
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر