2 papers
cs.DS2025
Online Firefighting on Cactus Graphs
Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu
It is known that the online firefighting is 2-competitive on trees (Coupechoux et al. 2019), which suggests that the problem is relatively easy on trees. We extend the study to gra…
cs.DS2025
On the FirstFit Algorithm for Online Unit-Interval Coloring
Bob Krekelberg, Alison Hsiang-Hsuan Liu
In this paper, we study the performance of the FirstFit algorithm for the online unit-length intervals coloring problem where the intervals can be either open or closed, which serv…