Name
Abstract | ||
|---|---|---|
The Firefighting problem is defined as follows. At time t=0, a fire breaks out at a vertex of a graph. At each time step t≥1, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.02.032 | Theoretical Computer Science |
Keywords | DocType | Volume |
Firefighting,Parameterized complexity,NP-complete,Kernelization | Journal | 782 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bireswar Das | 1 | 66 | 10.61 |
| Murali Krishna Enduri | 2 | 2 | 3.41 |
| Masashi Kiyomi | 3 | 204 | 17.45 |
| Neeldhara Misra | 4 | 341 | 31.42 |
| Yota Otachi | 5 | 161 | 37.16 |
| I. Vinod Reddy | 6 | 3 | 4.79 |
| Shunya Yoshimura | 7 | 0 | 0.34 |