Največji pretok po omrežju

diplomsko delo

Jure Cezar (Author), Andrej Brodnik (Mentor)

Abstract

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.

Keywords

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;

Data

Language:	Slovenian
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[J. Cezar]
UDC:	004(043.2)
COBISS:	1538527171
Views:	1513
Downloads:	183
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Maximum network flow
Secondary 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.
Secondary keywords:	network;complexity;maximal flow;algorithm;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	29 str.
ID:	11402140