کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874230 | 1441030 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The P3 infection time is W[1]-hard parameterized by the treewidth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The P3 infection time is W[1]-hard parameterized by the treewidth The P3 infection time is W[1]-hard parameterized by the treewidth](/preview/png/6874230.png)
چکیده انگلیسی
Recent papers investigated the maximum infection times tP3(G), tgd(G) and tmo(G) of the P3 convexity, geodesic convexity and monophonic convexity, respectively. In [4] and [8], it was proved that deciding whether tgd(G)â¥2 or tmo(G)â¥2 are NP-Complete problems even for bipartite graphs. In [17], it was proved that, in bipartite graphs, deciding whether tP3(G)â¥k is polynomial time solvable for kâ¤4, but is NP-Complete for kâ¥5. In this paper, we prove that the P3 infection time problem is fixed parameter tractable parameterized by treewidth + k, but is W[1]-hard when parameterized only by the treewidth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 132, April 2018, Pages 55-61
Journal: Information Processing Letters - Volume 132, April 2018, Pages 55-61
نویسندگان
Thiago Marcilon, Rudini Sampaio,