izpis_h1_title_alt

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

.pdfPDF - Presentation file, Download (307,57 KB)
MD5: 67523AE68668CA3C5E306C1A7E96796D
PID: 20.500.12556/rul/10665afa-f19f-426c-a956-b3b3417cad35

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
Organization:FRI - Faculty of Computer and Information Science
Year:2018
PID:20.500.12556/RUL-100178 This link opens in a new window
Publication date in RUL:12.03.2018
Views:1394
Downloads:511
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

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:

Back