Abstract
The maximum flow problem is one of the most basic problems in network flow theory. Many single-machine sequential algorithms are proposed over the years. However, distributed environments are much more common nowadays. In this thesis, our focus is to compute maximum flow on a distributed environment, where each distributed group may contain multiple computers running in parallel. We implement and evaluate three maximum-flow algorithms, including the Push-Relabel algorithm (the best sequential algorithm), a modified version of the Push-Relabel algorithm that is more communication-aware, and a recently proposed algorithm by Chen et al. [1] that is dedicated to run in a distributed environment.