Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Network reliability as a result of redundant connectivity
Thesis (MSc (Logistics)--University of Stellenbosch, 2007.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : University of Stellenbosch
2007
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614134095314944 |
|---|---|
| access_status_str | Open Access |
| author | Binneman, Francois J. A. |
| author2 | Van Vuuren, J. H. |
| author_browse | Binneman, Francois J. A. Van Vuuren, J. H. |
| author_facet | Van Vuuren, J. H. Binneman, Francois J. A. |
| author_sort | Binneman, Francois J. A. |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (MSc (Logistics)--University of Stellenbosch, 2007. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/1906 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:47:12.516Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2007 |
| publishDateRange | 2007 |
| publishDateSort | 2007 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/1906 Network reliability as a result of redundant connectivity Binneman, Francois J. A. Van Vuuren, J. H. University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics. Dissertations -- Logistics Theses -- Logistics Reliability (Engineering) Redundancy (Engineering) Graph theory Network reliability Connectivity algorithms 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. Masters 2007-11-12T06:24:29Z 2010-06-01T08:36:04Z 2007-11-12T06:24:29Z 2010-06-01T08:36:04Z 2007-03 Thesis http://hdl.handle.net/10019.1/1906 en University of Stellenbosch 1692963 bytes application/pdf application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Dissertations -- Logistics Theses -- Logistics Reliability (Engineering) Redundancy (Engineering) Graph theory Network reliability Connectivity algorithms Binneman, Francois J. A. Network reliability as a result of redundant connectivity |
| title | Network reliability as a result of redundant connectivity |
| title_full | Network reliability as a result of redundant connectivity |
| title_fullStr | Network reliability as a result of redundant connectivity |
| title_full_unstemmed | Network reliability as a result of redundant connectivity |
| title_short | Network reliability as a result of redundant connectivity |
| title_sort | network reliability as a result of redundant connectivity |
| topic | Dissertations -- Logistics Theses -- Logistics Reliability (Engineering) Redundancy (Engineering) Graph theory Network reliability Connectivity algorithms |
| url | http://hdl.handle.net/10019.1/1906 |
| work_keys_str_mv | AT binnemanfrancoisja networkreliabilityasaresultofredundantconnectivity |