Back to search

University of Glasgow

Parallel Algorithms for the Maximum Flow

Abstract

dc:description.abstract

The problem of finding the maximal flow through a given network has been intensively studied over the years. The classic algorithm for this problem given by Ford and Fulkerson has been developed and improved by a number of authors including Edmonds and Karp. With the advent of parallel computers, it is of great interest to see whether more efficient algorithms can be designed and implemented. The networks which we will consider will be both capacitated and bounded. Compared with a capacitated network, the problem of finding a flow through a bounded network is much more complicated in that a transformation into an auxiliary network is required before a feasible flow can be found. In this thesis, we review the algorithms of Ford and Fulkerson and Edmonds and Karp and implement them in a standard sequential way. We also implement the transformation required to handle the case of a bounded network. We then develop two parallel algorithms, the first being a parallel version of the Edmonds and Karp algorithm while the second applies the Breadth-First search technique to extract as much parallelism as possible from the problem. Both these algorithms have been written in the Occam programming language and implemented on a transputer system consisting of an IBM PC host, a B004 single transputer board and a network of four transputers contained on a B003 board supplied by Inmos Ltd. This is an example of a multiprocessor machine with independent memory. The relative efficiency of the algorithms has been studied and we present tables of the execution times taken over a variety of test networks. The transformation of the original network into an auxiliary network has also been implemented using parallel techniques and the problems encountered in the development of the algorithm are described. We have also investigated in detail one of the few parallel algorithms for this problem described in the literature due to Shiloach and Vishkin. This algorithm is described in the thesis. It has not been possible to implement this algorithm because it is specifically designed to run on a multiprocessor machine with shared memory.

Degree

thesis:*
Level dc:type.qualificationlevel
MSc(R)
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
1988

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Abdelouahab, Zair

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Abdelouahab, Zair. Parallel Algorithms for the Maximum Flow. MSc(R) thesis, University of Glasgow, 1988.