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

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...

Full description

Saved in:

Bibliographic Details
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
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.47935
record_format	uketd_dc
spelling	my-utm-ep.479352017-09-11T03:16:14Z Enhanced prim's algorithm for finding the hamiltonian cycle in a graph 2013-01 Dinon, Nur Atiqah QA Mathematics 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. 2013-01 Thesis http://eprints.utm.my/id/eprint/47935/ http://eprints.utm.my/id/eprint/47935/25/NurAtiqahDinonMFS2013.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Science Faculty of Science
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA Mathematics
spellingShingle	QA Mathematics Dinon, Nur Atiqah Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
description	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.
format	Thesis
qualification_level	Master's degree
author	Dinon, Nur Atiqah
author_facet	Dinon, Nur Atiqah
author_sort	Dinon, Nur Atiqah
title	Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
title_short	Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
title_full	Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
title_fullStr	Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
title_full_unstemmed	Enhanced prim's algorithm for finding the hamiltonian cycle in a graph
title_sort	enhanced prim's algorithm for finding the hamiltonian cycle in a graph
granting_institution	Universiti Teknologi Malaysia, Faculty of Science
granting_department	Faculty of Science
publishDate	2013
url	http://eprints.utm.my/id/eprint/47935/25/NurAtiqahDinonMFS2013.pdf
_version_	1747817267449561088

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

Similar Items