Return to search

A study and implementation of the network flow problem and edge integrity of networks

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

Identiferoai:union.ndltd.org:BSU/oai:cardinalscholar.bsu.edu:handle/184251
Date January 1991
CreatorsHaiba, Mohamed Salem
ContributorsBall State University. Dept. of Computer Science., Bagga, Kunwarjay S.
Source SetsBall State University
Detected LanguageEnglish
Formatv, 105 leaves : ill. ; 28 cm.
SourceVirtual Press

Page generated in 0.0015 seconds