A New Heuristic for the Hamiltonian Circuit Problem

Hamiltonian cycles;knight tour graphs;geometric graphs;random graphs;cubic cayley graphs;geometric graphs

Narayanasamy, Prabhu ; Dr. Carla Savage, Committee Member,Dr. Matthias Stallmann, Committee Chair,Dr. James Lester, Committee Member,Narayanasamy, Prabhu ; Dr. Carla Savage ; Committee Member ; Dr. Matthias Stallmann ; Committee Chair ; Dr. James Lester ; Committee Member

University:North Carolina State University

关键词: Hamiltonian cycles;    knight tour graphs;    geometric graphs;    random graphs;    cubic cayley graphs;    geometric graphs;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/166/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

In this research work, we have discussed a new heuristic for the Hamiltonian circuit problem. Our heuristic initially builds a small cycle in the given graph and incrementally expands the cycle by adding shorter cycles to it. We added features to our base heuristic to deal with the problems encountered during preliminary experiments. Most of our efforts were directed at cubic Cayley graphs but we also considered random, knight tour and geometric graphs.Our experimental results were mixed. In some but not all cases the enhancements improved performance. Runtime of our heuristic was generally not competitive with existing heuristics but this may be due to inefficient implementation. However, our experiments against geometric graphs were very successful and the performance was better than the Hertel’s SCHA algorithm, even in terms of runtime.