Parallelization of network flow algorithms
Ing. Václav Blažej
doc. Ing. Ivan Šimeček, Ph.D.
In this thesis we explore the possibilities of parallelization of several algorithms for finding the maximum flow in a network. We introduce necessary theoretical concepts and follow with a description of existing sequential and parallel algorithms. We present a new modification of Goldberg's algorithm suitable for parallelization on systems with shared memory. We then extend this algorithm to a scaling variant. All introduced algorithms are implemented in the C++ language and we measure their effectiveness on various input data.