کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421197 684158 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
3/2 firefighters are not enough
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
3/2 firefighters are not enough
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 1–2, January 2013, Pages 301–306
نویسندگان
, ,