20.500.12556/RUL-151096 Odpornost ovir na pravokotni domeni magistrsko delo Barrier Resilience in a Rectangular Domain 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. 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. računska geometrija odpornost ovir diskovni graf največji pretok najmanjši prerez computational geometry barrier resilience disk graph max-flow min-cut true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2023-09-29 08:15:10 2023-09-29 08:15:12 2024-05-29 12:39:57 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 138221 166764291 9832.pdf 9832.pdf 1 581D5946B8BDD30FBA94BDAA3CADE320 4e38139cc8253381369c97fbba56c45cde99c11a54e0a0c7ac4de2e48c52d5aa 8c092c9e-5e8f-11ee-8024-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=175988 9833.zip 9833.zip 1 2B338C0080D5934B0CC0F63F4DE27786 2b0d64a845ed2debacab59f5a14337ad2952c0688844c8749d3c11164908009e 8c0979ae-5e8f-11ee-8024-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=175989 Fakulteta za matematiko in fiziko Fakulteta za računalništvo in informatiko 0 0 0