Praktyczna implementacja algorytmu dla problemu maksymalnego przepływu z użyciem przepływów elektrycznych.

Problem maksymalnego przepływu można uznać za klasyczny problem w informatyce. Przedstawiona praca jest przewodnikiem po implementacji algorytmu o złożoności zaproponowany przez Mądrego w "Computing maximum flow with augmenting electrical flows", dla problemu maksymalnego s-t przepływu. Algorytm ten wykorzystuje interesujące narzędzia, takie jak obliczenia przepływu elektrycznego w oparciu o macierz Laplace'a bazowego grafu rezydualnego, optymalizację schematu prymalno-dualnego oraz interesującą technika zaokrąglania. Głównym celem było przekształcenie wspomnianej pracy w możliwe do implementacji kroki algorytmu i zbadanie, czy możliwe jest efektywne zaimplementowanie algorytmu we współczesnym języku programowania i podjęcie decyzji o jego możliwości jego praktycznego zastosowania. Dodatkowo w ramach tych prac powstała implementacja wspomnianego algorytmu w języku programowania c++.

The maximum flow problem can be considered as a classic problem in computer science. The presented thesis is an implementation guide for -time algorithm, proposed by Madry in "Computing maximum flow with augmenting electrical flows", for the maximum s-t flow problem. This algorithm employs interesting tools such as electrical flow computation based on Laplacian of the underlying residual graph, primal-dual optimization, and an interesting rounding technique. The main goal was to transform the mentioned work into implementable algorithm steps and to investigate whether it is possible to effectively implement the algorithm in a modern programming language and decide on its applicability in practice. Additionally, as part of this work, an implementation of the algorithm mentioned above was created in the c++ programming language.