کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427014 | 686422 | 2013 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial kernels for Proper Interval Completion and related problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a graph G=(V,E)G=(V,E) and a positive integer k, the Proper Interval Completion problem asks whether there exists a set F of at most k pairs of (V×V)∖E(V×V)∖E such that the graph H=(V,E∪F)H=(V,E∪F) is a proper interval graph. The Proper Interval Completion problem finds applications in molecular biology and genomic research. This problem is known to be FPT (Kaplan, Tarjan and Shamir, FOCSʼ94), but no polynomial kernel was known to exist. We settle this question by proving that Proper Interval Completion admits a kernel with O(k3)O(k3) vertices. Moreover, we prove that a related problem, the so-called Bipartite Chain Deletion problem, admits a kernel with O(k2)O(k2) vertices, completing a previous result of Guo (ISAACʼ07).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 231, October 2013, Pages 89–108
Journal: Information and Computation - Volume 231, October 2013, Pages 89–108
نویسندگان
Stéphane Bessy, Anthony Perez,