### DIMACS Computational and Mathematical Epidemiology Seminar Series

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.