Finding Hamiltonian cycles: An algorithm
Date of Publication
2008
Document Type
Bachelor's Thesis
Degree Name
Bachelor of Science in Mathematics with Specialization in Computer Applications
Subject Categories
Mathematics
College
College of Science
Department/Unit
Mathematics and Statistics
Thesis Adviser
Severino Gervacio
Defense Panel Chair
Isagani B. Jos
Defense Panel Member
Gaudencio C. Petalcorin, Jr.
Rigor B. Ponsones
Abstract/Summary
Dirac's famous theorems states that If G is a graph of order () 3 such that the minimum degree (), then G is Hamiltonian. This paper presents a constructive proff of this theorem based on the C++ algorithm that finds a Hamiltonian cycle given the same conditions as the theorem. In addition, the complexity of the algorithm was also examined to evaluate if the algorithm is a P-problem or NP-problem class.
Mainly, this paper is an exposition of the article A New Algorithm For Finding Hamiltonian Circuits by Ashay Dharwadker."
Abstract Format
html
Language
English
Format
Accession Number
TU13566
Shelf Location
Archives, The Learning Commons, 12F, Henry Sy Sr. Hall
Physical Description
vi, 62 leaves, illustrations, 28 cm.
Keywords
Hamiltonian graph theory
Recommended Citation
Macapagal, R. R., & Tan, M. T. (2008). Finding Hamiltonian cycles: An algorithm. Retrieved from https://animorepository.dlsu.edu.ph/etd_bachelors/5054
Embargo Period
3-29-2021
