izpis_h1_title_alt

Algoritmi problema pretokov
AJDIČ, GREGOR (Author), Robič, Borut (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (307,57 KB)

Abstract
Predpostavimo, da je naš namen prenesti nek material od izvora do ponora preko vozlišč. Na naši poti imamo povezave, ki imajo maksimalno kapaciteto. Naš cilj je ugotoviti, največ koliko materiala lahko prenesemo od izvora do ponora, brez da bi kršili kapacitetne omejitve. Reševanje tega problema je bilo sprva možno s splošnimi tehnikami linearnega programiranja, kasneje pa so se začeli razvijati številni drugi algoritmi. Nekateri izmed njih uporabljajo pristope in metode, ki so zanimivi s teoretičnega vidika, drugi pa so primernejši za uporabo v praksi. Cilji diplomskega dela so predstavitev glavnih idej teh algoritmov, njihova analiza in prikaz nekaterih praktičnih primerov. Želimo ugotoviti, kateri algoritem je trenutno najhitrejši.

Language:Slovenian
Keywords:pretok, omrežje pretokov, rezidualno omrežje, nenasičene poti, rezi, blokiranje poti, dinamična drevesa, metoda potiska in ponovnega označevanja, obilni graf
Work type:Bachelor thesis/paper (mb11)
Organization:FRI - Faculty of computer and information science
Year:2018
Views:377
Downloads:335
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Network Flow Algorithms
Abstract:
Let us assume that it is our intention to transfer material from source to sink through the nodes of a graph. Each edge has a certain capacity. Our goal is to determine how much material can be transferred from the source to the sink without violating the capacity limit. Initially basic linear programming techniques were used to solve this problem, but later many other algorithms were discovered. Some of them use approaches and methods that are interesting from a theoretical point of view, while others are more suitable for practical use. The aims of the thesis are the presentation of these algorithms, their analysis and the display of basic examples. We want to figure out which algorithm is currently the fastest in solving this problem.

Keywords:flow, network flow, residual network, augmenting paths, cuts, blocking path, dynamic trees, push relabel method, abundance graph

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back