کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421335 | 684201 | 2008 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Closest 4-leaf power is fixed-parameter tractable
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most rr edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree—the 4-leaf root—with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we give the first algorithmic result for Closest 4-Leaf Power, showing that Closest 4-Leaf Power is fixed-parameter tractable with respect to the parameter rr.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 18, 28 November 2008, Pages 3345–3361
Journal: Discrete Applied Mathematics - Volume 156, Issue 18, 28 November 2008, Pages 3345–3361
نویسندگان
Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier,