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

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