کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419647 | 683846 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized graph cleaning problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)||V(G)|−|V(H)| with HH and GG being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph GG, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph HH representing the original pattern. We show fixed-parameter tractability of the cases where both HH and GG are planar and HH is 3-connected, or HH is a tree and GG is arbitrary. We also prove that the problem when HH and GG are both 3-connected planar graphs is NP-complete without parameterization.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3258–3267
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3258–3267
نویسندگان
Dániel Marx, Ildikó Schlotter,