Bachelor theses
Parallelization of network flow algorithms
Author
Jan Groschaft
Year
2019
Type
Bachelor thesis
Supervisor
Ing. Václav Blažej
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
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.