The research presented in this thesis investigates the performance of some well-known heuristic algorithms on graph decomposition problems. First, a genetic algorithm is introduced and some modifications are trialled on finding Steiner triple systems (STS) of small orders. The results show that traditional genetic algorithms are not well suited to finding graph decompositions. Then a hill climbing optimisation technique is presented and investigated in the context of cycle decompositions. Such searches have previously proved to be effective at finding STSs. However, the general hill climbing approach is not immediately applicable to decompositions into cycles of length larger than 3. A modification of the hill climbing algorithm for cycles, called slippery hill climbing, is introduced and tested on decompositions of graphs into cycles of small lengths larger than 3. Slippery hill climbing successfully decomposed complete and dense non-complete graphs of considerable sizes into cycles of small lengths. In addition, we applied the slippery hill climbing approach to completing partial latin squares. It is reasonably expected that the algorithms developed in this study will also be applicable to other related problems in combinatorics and graph theory.
| Identifer | oai:union.ndltd.org:ADTP/253982 |
| Creators | Andriy Kvyatkovskyy |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.0019 seconds