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

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
نویسندگان
, ,