Enhanced prim's algorithm for finding the hamiltonian cycle in a graph

• Main Author: Dinon, Nur Atiqah
• Format: Thesis
• Language: English
• Published: 2013
• Subjects: QA Mathematics
• Online Access: http://eprints.utm.my/id/eprint/47935/25/NurAtiqahDinonMFS2013.pdf; http://eprints.utm.my/id/eprint/47935/
• Institution: Universiti Teknologi Malaysia

The Travelling Salesman Problem (TSP) is known as one of the oldest combinatorial optimisation problem which solves the path problem in weighted graph. With the main objective to visiting all places (nodes) in a round trip that start and end in one specific place, TSP shared the same problem with a lot of applications in the world nowadays. In short, the goal of TSP is to find a Hamiltonian cycle. Hamiltonian cycle was introduced in 1800’s which is as old as the moment TSP captured the mind of the thinker. Lots of great and major discussions have been made till now and TSP has seen applications in the areas of logistics, genetics, manufacturing, telecommunications, neuroscience and many more. TSP has been intervening in many of the everyday experience by most people and not only for a salesman. Be it a usual errand around the house or the major project by the company or government, TSP has an innate connection in tour finding which lead the attention from various personnel. In another related graph problem, Prim’s Algorithm (PA) is widely used to compute the Minimum Spanning Tree (MST) of a graph. In this research, the two algorithms are being related by modifying the PA in order to work out the TSP which will find the Hamiltonian cycle of the graph. This new approach is called Enhanced Prim’s Algorithm (EPA) which solves the TSP for fast result.