izpis_h1_title_alt

Gomory-Hu drevesa
ID ŠETINA, TOMAŽ (Author), ID Fijavž, Gašper (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (435,22 KB)
MD5: 02E10EB98EED23773A056011E88DF120

Abstract
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.

Language:Slovenian
Keywords:Gomory-Hu drevo, maksimalni pretok, minimalni prerez, minimalni k-prerez, dinamični grafi
Work type:Bachelor thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2018
PID:20.500.12556/RUL-101264 This link opens in a new window
Publication date in RUL:18.05.2018
Views:1473
Downloads:440
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Gomory-Hu trees
Abstract:
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.

Keywords:Gomory-Hu tree, max flow, min cut, min k-cut, dynamic graphs

Similar documents

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

Back