| dc.rights.license | CC-BY-NC-ND | |
| dc.contributor.advisor | Liu, Alison | |
| dc.contributor.author | Hugen, Max | |
| dc.date.accessioned | 2025-08-15T00:03:55Z | |
| dc.date.available | 2025-08-15T00:03:55Z | |
| dc.date.issued | 2025 | |
| dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/49753 | |
| dc.description.abstract | The FIREFIGHTER problem is a turn-based game on a graph in which a spreading fire must be contained by protecting vertices. We study the online variant, where each decision is made without knowledge of future events. While previous research has established an optimal 2-competitive algorithm for trees, we extend the analysis to cactus graphs. For this class, we present an O(√n)-competitive algorithm and prove, via a matching lower bound, that it is optimal. We then analyze a variant where an even number of firefighters is released each round (a multiple of the treewidth 2). We show that under this restriction the competitive ratio drops from O(√n) to a constant: a greedy algorithm is exactly 3-competitive. | |
| dc.description.sponsorship | Utrecht University | |
| dc.language.iso | EN | |
| dc.subject | The FIREFIGHTER problem is a turn-based game on a graph in which a spreading fire must be contained by protecting vertices. We study the online variant, where each decision is made without knowledge of future events, on cactus graphs. For this class, we present an O(√n)-competitive algorithm and prove, via a matching lower bound, that it is optimal. We then show that in a variant where an even number of firefighters is released each round, the greedy algorithm is 2-competitive. | |
| dc.title | Online Firefighting on Cactus Graphs | |
| dc.type.content | Master Thesis | |
| dc.rights.accessrights | Open Access | |
| dc.subject.keywords | Online algorithms; FIREFIGHTER problem; graph algorithms; combinatorial
optimization; competitive analysis | |
| dc.subject.courseuu | Computing Science | |
| dc.thesis.id | 51685 | |
