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