The Hamiltonian cycle problem (HCP) can be succinctly stated as: "Given a graph, find a cycle that passes through every single vertex exactly once, or determine that this cannot be achieved". Such a cycle is called a Hamiltonian cycle. The HCP is a special case of the better known Travelling salesman problem, both of which are computationally difficult to solve. An efficient solution to the HCP would help solving the TSP effectively, and therefore would have a great impact in various fields such as computer science and operations research. In this thesis, we obtain novel theoretical results that approach this discrete, deterministic, problem using tools from stochastic processes, matrix analysis, and graph theory. / PhD Doctorate
Identifer | oai:union.ndltd.org:ADTP/269002 |
Date | January 2009 |
Creators | Nguyen, Giang Thu |
Source Sets | Australiasian Digital Theses Program |
Language | EN-AUS |
Detected Language | English |
Rights | Copyright Giang T. Nguyen 2009 |
Page generated in 0.0019 seconds