Algorithms for Maximal Flow Problems

Abstract

Network flows are growing interest from the point of view of both application and theory. The topic of network flows has application in such as diverse fields as engineering, management, Science, Computer Science to name but a few. Related to theory, network flow have been proven to be excellent indicator of things to come in mathematical programming.Maximum flow problem is a classical network flow problem. In general, there are two principal categories for solving the maximum problem, the labelling method and preflow-push method. The labelling method increase the flow along augmentation path from source node to sink node. The idea of preflow-push algorithm is to seek out the shortest path as in the labelling method, but do not send flow along paths from source node to sink node.Present thesis deals the algorithm for the maximal flow problems. The thesis contains four chapters. Chapter one is introductory in nature in which the terminology needed to discuss the maximal flow problem and brief survey on literature related to the topic have been discussed. In chapter two, “On critical capacity on arcs in a directed network” given by Sonia and Puri (2006) is reviewed. In chapter three, the cut search algorithm with arc capacity and lower bounds given by Phillips and Dessouky (1979) is reviewed. In chapter four, an attempt has been made to apply the algorithm given by Sonia and Puri (2006) to a network in which the network is undirected.