| Type of Document |
Dissertation |
| Author |
Shields, Ian Beaumont, |
| Author's Email Address |
ishields@us.ibm.com |
| URN |
etd-03142004-013420 |
| Title |
Hamilton Cycle Heuristics in Hard Graphs |
| Degree |
PhD |
| Graduate Program |
Computer Science |
| Advisory Committee |
| Advisor Name |
Title |
| Carla D. Savage |
Committee Chair |
| Jon Doyle |
Committee Member |
| Matthias F. Stallmann |
Committee Member |
| Robert E. Hartwig |
Committee Member |
|
| Keywords |
- Hamilton cycle algorithms
- graph theory
|
| Date of Defense |
2004-03-03 |
| Availability |
unrestricted |
Abstract
In this thesis, we use computer methods to investigate Hamilton cycles and paths in several families of graphs where general results are incomplete, including Kneser graphs, cubic Cayley graphs and the middle two levels graph. We describe a novel heuristic which has proven useful in finding Hamilton cycles in these families and compare its performance to that of other algorithms and heuristics. We describe methods for handling very large graphs on personal computers. We also explore issues in reducing the possible number of generating sets for cubic Cayley graphs generated by three involutions.
|
| Files |
| Filename |
Size |
Approximate Download Time
(Hours:Minutes:Seconds)
|
| 28.8 Modem |
56K Modem |
ISDN (64 Kb) |
ISDN (128 Kb) |
Higher-speed Access |
| |
etd.pdf |
915.03 Kb |
00:04:14 |
00:02:10 |
00:01:54 |
00:00:57 |
00:00:04 |
|
