Title: A survey of some results on the Firefighter Problem
Speaker: Kah Loon Ng, DIMACS
Date: March 21, 2005 2:30 - 3:45 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
One of the simplest disease spread mechanism that Epidemiologists have proposed is that of a perfectly contagious disease with no cure. In this model, vertices adjacent to infected vertices become infected at every discrete time step, and once infected, a vertex remains infected for the entire duration of study. As a response to this disease spread, we have a limited number of vaccinations that we can use on non-infected vertices. The general objective is to find an optimal strategy for vaccinating non-infected vertices such that the number of infected vertices is minimized. This simple model is equivalent to a problem of fire spreading in a network introduced by Hartnell, known as the Firefighter Problem. In this talk, I shall survey some results relating to the Firefighter Problem and its variants.