3/2 Firefighters are not enough

Details 3/2 Firefighters are not enough 3/2 Firefighters are not enough

2010-05-11

arxiv.org/abs/1005.1694v1

Computer Science

Discrete Mathematics

8 pages

Scientific paper

The firefighter problem is a monotone dynamic process in graphs that can be viewed as modeling the use of a limited supply of vaccinations to stop the spread of an epidemic. In more detail, a fire spreads through a graph, from burning vertices to their unprotected neighbors. In every round, a small amount of unburnt vertices can be protected by firefighters. How many firefighters per turn, on average, are needed to stop the fire from advancing? We prove tight lower and upper bounds on the amount of firefighters needed to control a fire in the Cartesian planar grid and in the strong planar grid, resolving two conjectures of Ng and Raff.

Affiliated with

Also associated with

No associations

Rating

3/2 Firefighters are not enough does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with 3/2 Firefighters are not enough, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3/2 Firefighters are not enough will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-383361