Complexity of Firefighting on Graphs

Julius Althoetmar, Jamico Schade, Torben Schürenberg

We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters requ…