کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871113 | 1440178 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Flood-It is a combinatorial problem on a colored graph whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a pivot vertex p. A flooding move consists of changing the color of the monochromatic component (maximal monochromatic connected subgraph) containing p. This problem generalizes a combinatorial game named alike which is played on mÃn grids. It is known that Flood-It is NP-hard even for 3Ãn grids and for instances with bounded number of colors, diameter, treewidth, or pathwidth. In [Fellows, Souza, Protti, Dantas da Silva, Tractability and hardness of flood-filling games on trees, Theoretical Computer Science, 576, 102-116, 2015] it is shown that Flood-It is W[1]-hard when played on trees with bounded number of colors, and the number of leaves is a single parameter. Contrasting with such results, in this work we show that Flood-It is fixed-parameter tractable when parameterized by either the vertex cover number or the neighborhood diversity. Additionally, we prove that Flood-It does not admit a polynomial kernel when the vertex cover number is a single parameter, unless coNPâNPâpoly. Finally, lower bounds based on the (Strong) Exponential Time Hypothesis as well as an upper bound for the required time to solve Flood-It are also provided.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 94-100
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 94-100
نویسندگان
Michael Fellows, Fábio Protti, Frances Rosamond, Maise Dantas da Silva, Uéverton S. Souza,