کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871774 | 1440191 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Burning a graph is hard
ترجمه فارسی عنوان
سوزاندن یک نمودار سخت است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP-complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 73-87
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 73-87
نویسندگان
Stéphane Bessy, Anthony Bonato, Jeannette Janssen, Dieter Rautenbach, Elham Roshanbin,