Fundamental problems in graph theory are of four types existence, construction, enumeration and optimization problems. Optimization problems lie at the interface between computer science and the field of operations research and are of primary importance in decision-making. In this thesis, two optimization problems are studied: the edge-integrity of networks and the network flow problem. An implementation of the corresponding algorithms is also realized.The edge integrity of a communication network provides a way to assess the vulnerability of the network to disruption through the destruction or failure of some of its links. While the computation of the edge-integrity of graphs in general has been proven to be NPcomplete, a recently published paper was devoted to a good algorithm using a technique of edge separation sequence for computing the edge integrity of trees. The main results of this paper will be presented and an implementation of this algorithm is achieved.The network flow problem models a distribution system in which commodities are flowing through an interconnected network. The goal is to find a maximum feasible flow and its value, given the capacity constraints for each edge. The three majors algorithms for this problem (Ford -Fulkerso n, Edmonds-Karp method, MPKM algorithm) are discussed, their complexities compared and an implementation of the Ford-Fulkerson and the MPKM algorithms is presented. / Department of Computer Science
| Identifer | oai:union.ndltd.org:BSU/oai:cardinalscholar.bsu.edu:handle/184251 |
| Date | January 1991 |
| Creators | Haiba, Mohamed Salem |
| Contributors | Ball State University. Dept. of Computer Science., Bagga, Kunwarjay S. |
| Source Sets | Ball State University |
| Detected Language | English |
| Format | v, 105 leaves : ill. ; 28 cm. |
| Source | Virtual Press |
Page generated in 0.0015 seconds