Tytuł pozycji:
Practical implementation of Maximum Flow algorithm with Electrical Flows.
- Tytuł:
-
Practical implementation of Maximum Flow algorithm with Electrical Flows.
Praktyczna implementacja algorytmu dla problemu maksymalnego przepływu z użyciem przepływów elektrycznych.
- Autorzy:
-
Pabian, Mateusz
- Słowa kluczowe:
-
graph, graph theory, network flows, maximum flow problem, max s-t flow problem, residual graph, electrical flow, Laplacian, laplacian systems, dynamic trees, splay tree, rounding fractional flow, acyclic flow problem, matching, b-matching, perfect matching, continuous optimization, duality, primal-dual scheme, algorithms, computational complexity, implementation, c++.
graf, teoria grafów, sieci przepływowe, problem maksymalnego przepływu, problem maksymalnego s-t przepływu, graf residualny, przepływ elektryczny, macierz Laplace'a, układ równań Laplace'a, drzewa dynamiczne, drzewo splay, drzewo rozchylane, zaokrąglanie przepływu niecałkowitego, problem przepływ bez cykli, skojarzenie, b-skojarzenie, skojarzenie doskonałe, optymalizacja ciągła, dualność, schemat prymalno-dualny, algorytmika, złożoność obliczeniowa, implementacja, c++.
- Język:
-
angielski
- Dostawca treści:
-
Repozytorium Uniwersytetu Jagiellońskiego
-
Przejdź do źródła Link otwiera się w nowym oknie
Problem maksymalnego przepływu można uznać za klasyczny problem w informatyce. Przedstawiona praca jest przewodnikiem po implementacji algorytmu o złożoności $~O(m^10/6 U^1/7)$ 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 $~O(m^10/6 U^1/7)$-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.
