Parallel implementation of flow and matching algorithms

W pracy są zaprezentowane dwa równoległe algorytmy oraz ich implementacje lock-free, wykorzystujące równoległą architekturę GPU Nvidia CUDA. Pierwszy z nich, to algorytm push-relabel obliczający przepływ w grafie gridowym. Drugi, to algorytm skalowania kosztów dla problemu skojarzenia ważonego w pełnym grafie dwudzielnym.

In our work we present two parallel algorithms and their lock-free implementations using a popular GPU environment Nvidia CUDA. The first algorithm is the push-relabel method for the flow problem in grid graphs. The second is the cost scaling algorithm for the assignment problem in complete bipartite graphs.