izpis_h1_title_alt

Gomory-Hu drevesa
ŠETINA, TOMAŽ (Avtor), Fijavž, Gašper (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (435,22 KB)

Izvleček
Klasični Ford-Fulkersonov rezultat zlepi problema maksimalnega u-v pretoka in minimalnega u-v prereza med izbranima vozliščema u in v v omrežju - uteženem grafu. V diplomski nalogi se ukvarjamo s problemom Gomory-Hu drevesa, ki v eni sami drevesni strukturi hrani informacijo o vseh minimalnih prerezih v grafu. Natančneje, iskanje minimalnega prereza med poljubnima vozliščema u in v v omrežju lahko predstavimo z iskanjem drevesne povezave z najmanjšo vrednostjo prepustnosti na edini poti med istima vozliščema v Gomory-Hu drevesu. V delu implementiramo Gusfieldov algoritem za izračun Gomory-Hu drevesa in ga časovno ovrednotimo. Zaradi velike časovne zahtevnosti izračuna Gomory-Hu drevesa implementiramo algoritem za dinamičen izračun novega drevesa iz obstoječega drevesa pri spremembi prepustnosti posamezne povezave v grafu G. Izkaže se, da je algoritem za izračun drevesa pri povečanju prepustnosti povezave v grafu G hitrejši v primerjavi z osnovnim algoritmom. V primeru zmanjšanja prepustnosti povezave ne pride do kvalitativnih razlik.

Jezik:Slovenski jezik
Ključne besede:Gomory-Hu drevo, maksimalni pretok, minimalni prerez, minimalni k-prerez, dinamični grafi
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2018
Število ogledov:528
Število prenosov:317
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Gomory-Hu trees
Izvleček:
The classical Ford-Fulkerson algorithm computes a maximum u-v flow and a minimum u-v cut between two selected nodes u, v from flow network - weighted graph. In this thesis we study Gomory-Hu trees which in one tree structure include information about all minimum in the graph. More precisely computing a minimum cut between a pair of nodes u and v nodes in flow network can be reduced to searching for an edge with smallest capacity in the unique u-v path in the Gomory-Hu tree. We implement and evaluate Gusfield algorithm for computing Gomory-Hu tree. The presented algorithm for computing Gomory-Hu trees has relatively high time complexity, so we also implement an algorithm for dinamically computing Gomory-Hu trees following a capacity change in the graph. It turns out that in the case of increasing capacity the dynamic approach outperforms the basic algorithm. However, we measure no substantial improvement in the case of reducing capacity of an edge.

Ključne besede:Gomory-Hu tree, max flow, min cut, min k-cut, dynamic graphs

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj