Date of Award
Spring 2026
Degree Type
Honors College Thesis
Academic Program
Computer Science BS
Department
Computing
First Advisor
Bernd Schröder, Ph.D.
Advisor Department
Computing
Abstract
The Hamiltonian cycle problem is ubiquitous in both computer science and graph theory: Given a connected graph, a solution would either confirm the existence of a cycle which visits each vertex only once or its nonexistence. The importance of this problem, as well as its difficulty, is described in the Clay Mathematics Institute’s Millenium Prize Problems and Karp’s 21 NP-complete problems. Despite its “hardness,” solutions to the Hamiltonian cycle problem are desired in logistics, electronic circuit design, and network routing, among other fields. In this work, we benchmark a promising exhaustive enumeration algorithm on various graphs, including ones derived from research at the University of Southern Mississippi, in the pursuit to both validate findings from previous research as well as identify graph characteristics inherent to the problem’s difficulty.
Copyright
Copyright for this thesis is owned by the author. It may be freely accessed by all users. However, any reuse or reproduction not covered by the exceptions of the Fair Use or Educational Use clauses of U.S. Copyright Law or without permission of the copyright holder may be a violation of federal law. Contact the administrator if you have additional questions.
Recommended Citation
Davis, Chance, "Algorithm Performance in the Search for Hamiltonian Cycles" (2026). Honors Theses. 1088.
https://aquila.usm.edu/honors_theses/1088