Odpornost ovir na pravokotni domeni : magistrsko delo

Marinko, Matej (avtor), Cabello Justo, Sergio (mentor)

Magistrsko delo obravnava problem odpornosti ovir na pravokotni domeni. Najprej predstavimo algoritme za izračun največjega pretoka in najmanjšega prereza v omrežjih. Nato predstavimo problem odpornosti ovir, kjer se najbolj osredotočimo na problem odpornosti ovir na pravokotni domeni. Problem prevedemo na problem iskanja največjega pretoka. Algoritem še dodatno optimiziramo, da se izognemo eksplicitni konstrukciji grafov. Ogledamo si tudi sorodne probleme, ki jih lahko z manjšimi spremembami reši predstavljeni algoritem. Predstavljeni algoritem tudi implementiramo. Implementacija omogoča preučevanje obnašanja problema na različnih množicah diskov in preučevanje časovne zahtevnosti različnih implementacij algoritma v praksi.

• Jezik: Slovenski jezik
• Ključne besede: računska geometrija, odpornost ovir, diskovni graf, največji pretok, najmanjši prerez
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko ; FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2023
• PID: 20.500.12556/RUL-151096
• COBISS.SI-ID: 166764291
• Datum objave v RUL: 29.09.2023

MARINKO, Matej, 2023, Odpornost ovir na pravokotni domeni : magistrsko delo [na spletu]. Magistrsko delo. [Dostopano 26 april 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=151096

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Barrier Resilience in a Rectangular Domain

Izvleček

The master's thesis addresses the problem of barrier resilience in a rectangular domain. First, we introduce algorithms for computing maximum flows and minimum cuts in networks. Then, we present the barrier resilience problem with a primary focus on the variant of the problem in a rectangular domain. We reduce the problem to a maximum flow problem and further optimize the algorithm to avoid explicit graph constructions. We also explore related problems that can be solved using the presented algorithm with minor modifications. The algorithm presented is also implemented. The implementation allows us to study the behavior of the problem on various sets of disks and to examine the time complexity of different algorithm implementations in practice.

• Ključne besede: computational geometry, barrier resilience, disk graph, max-flow, min-cut