Največji pretok po omrežju

diplomsko delo

Jure Cezar (Avtor), Andrej Brodnik (Mentor)

Povzetek

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.

Ključne besede

omrežje;zahtevnost;največji pretok;algoritem;računalništvo;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[J. Cezar]
UDK:	004(043.2)
COBISS:	1538527171
Št. ogledov:	1513
Št. prenosov:	183
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Maximum network flow
Sekundarni povzetek:	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.
Sekundarne ključne besede:	network;complexity;maximal flow;algorithm;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	29 str.
ID:	11402140