Thesis (MSc (Logistics)--University of Stellenbosch, 2007. / There exists, for any connected graph G, a minimum set of vertices that, when removed, disconnects
G. Such a set of vertices is known as a minimum cut-set, the cardinality of which is known as the
connectivity number k(G) of G. A connectivity preserving [connectivity reducing, respectively] spanning
subgraph G0 ? G may be constructed by removing certain edges of G in such a way that k(G0) = k(G)
[k(G0) < k(G), respectively]. The problem of constructing such a connectivity preserving or reducing
spanning subgraph of minimum weight is known to be NP–complete.
This thesis contains a summary of the most recent results (as in 2006) from a comprehensive survey of
literature on topics related to the connectivity of graphs.
Secondly, the computational problems of constructing a minimum weight connectivity preserving or
connectivity reducing spanning subgraph for a given graph G are considered in this thesis. In particular,
three algorithms are developed for constructing such spanning subgraphs. The theoretical basis for each
algorithm is established and discussed in detail. The practicality of the algorithms are compared in terms
of their worst-case running times as well as their solution qualities. The fastest of these three algorithms
has a worst-case running time that compares favourably with the fastest algorithm in the literature.
Finally, a computerised decision support system, called Connectivity Algorithms, is developed which is
capable of implementing the three algorithms described above for a user-specified input graph.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/1906 |
| Date | 03 1900 |
| Creators | Binneman, Francois J. A. |
| Contributors | Van Vuuren, J. H., University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1692963 bytes, application/pdf |
| Rights | University of Stellenbosch |
Page generated in 0.0024 seconds