کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433857 689640 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Planar graph is on fire
ترجمه فارسی عنوان
نمودار پلانار بر روی آتش است
کلمات کلیدی
مشکل آتش نشانی نرخ زنده ماندن، نمودار پلانار
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let G be any connected graph on n   vertices, n≥2n≥2. Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn k firefighters can protect vertices of G — each can protect one vertex not yet on fire; Next the fire spreads to all unprotected neighbours.The k-surviving   rate of G, denoted by ρk(G)ρk(G), is the expected fraction of vertices that can be saved from the fire by k firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph G   we have ρ3(G)≥221. Moreover, 3 firefighters are needed for the first step only; after that it is enough to have 2 firefighters per each round. This result significantly improves the known solutions to a problem by Cai and Wang (there was no positive bound known for the surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 160–164
نویسندگان
,