"The topology of a network (such as a telecommunications, multiprocessor, or local area network, to name just a few) is usually modelled by a graph in which vertices represent 'nodes' (stations or processors) while undirected or directed edges stand for 'links' or other types of connections, physical or virtual. A cycle that contains every vertex of a graph is called a hamiltonian cycle and a graph which contains a hamiltonian cycle is called a hamiltonian graph. The problem of the existence of a hamiltonian cycle is closely related to the well known problem of a travelling salesman. These problems are NP-complete and NP-hard, respectively. While some necessary and sufficient conditions are known, to date, no practical characterization of hamiltonian graphs has been found. There are several ways to generalize the notion of a hamiltonian cycle. In this thesis we make original contributions in two of them, namely k-walks and r-trestles." --Abstract. / Doctor of Philosophy
| Identifer | oai:union.ndltd.org:ADTP/266045 |
| Date | January 2008 |
| Creators | Teska, Jakub |
| Publisher | Author |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
| Rights | Copyright Jakub Teska |
Page generated in 0.0012 seconds