Največji pretok po omrežju

CEZAR, JURE (author), Brodnik, Andrej (mentor)

Namen dela je seznaniti bralca o algoritmih za iskanje največjega pretoka v omrežjih. Opisuje tri vrste algoritmov, njihovo delovanje in analizo. Prvi algoritem je Ford-Fulkersonov algoritem, ki je bil eden izmed prvih algoritmov za iskanje največjega pretoka. Drugi algoritem je zaporedni potisni in preimenuj, ki je eden izmed najhitrejših zaporednih algoritmov v današnjem času. Tretji algoritem je vzporedni potisni in preimenuj algoritem, ki je vzporedna pohitritev zaporednega potisni in preimenuj algoritma. Poleg algoritmov je v drugem poglavju opisana teorija omrežij, za lažje razumevanje delovanja algoritmov. V petem poglavju so zajeti vsi rezultati. Na začetku je časovna primerjava vseh treh algoritmov. V nadaljevanju se rezultati osredotočijo zgolj na vzporedni potisni in preimenuj algoritem, saj nas je zanimala pohitritev zaporednega potisni in preimenuj algoritma z vzporednim procesiranjem ter vplivom števila procesorjev na izvajanje vzporednega potisni in preimenuj algoritma. Pohitritev zaporednega algoritma se je kljub počasnejšemu delovanju na omrežjih z manj vozlišči izkazala za uspešno. Na omrežjih z velikim številom vozlišč smo zaporedni potisni in preimenuj algoritem pohitrili do 4-krat. Vzporedni potisni in preimenuj algoritem bi lahko še bolje optimizirali in s tem še dodatno pohitrili izvajanje, vendar to ni cilj te diplomske naloge.

• Language: Slovenian
• Keywords: omrežje, zahtevnost, največji pretok, algoritem
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2020
• PID: 20.500.12556/RUL-113861
• COBISS.SI-ID: 1538527171
• Publication date in RUL: 07.02.2020

Secondary language

• Language: English
• Title: Maximum network flow

Abstract

The purpose of the work is to acquaint the reader about algorithms for finding the maximum flow in networks. It describes three types of algorithms, their implementations and analysis. First algorithm is Ford-Fulkerson which was one of the first algorithms for finding maximum flow in networks. Second algorithm is sequential push-relabel algorithm which is one of the fastest sequential algorithms for finding maximum flow in networks at the time. Third algorithm is parallel push-relabel algorithm which is parallel speed up of sequential push-relabel algorithm. In addition to algorithms, Chapter 2 describes network theory to help understand how algorithms work. Chapter 5 covers all the results. In the beginning, there is a time comparison of all three algorithms. Then the results focus only on the parallel push-relabel algorithm, since we were interested in speeding up the sequential push-relabel by parallel processing and the impact of the number of processors on running the parallel push-relabel algorithm. Speeding up the sequential algorithm has proven to be successful, despite slower performance on networks with fewer nodes. On networks with many nodes, the sequential push-relabel algorithm was speeded up to 4 times. The parallel push-relabel algorithm could be further optimized to better speed up imprementation, but this was not the goal of this thesis.

• Keywords: network, complexity, maximal flow, algorithm