کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874677 | 1441188 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Unit interval vertex deletion: Fewer vertices are relevant
ترجمه فارسی عنوان
حذف نسخه عددی واحد: واحدهای کمتر مرتبط هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار فاصله واحد کرنل کردن، مشکل اصلاح نمودار زیرگرافی القا شده ممنوع (مدل مناسب، واحد)، مدولاتور،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The unit interval vertex deletion problem asks for a set of at most k vertices whose deletion from a graph makes it a unit interval graph. We develop an O(k4)-vertex kernel for the problem, significantly improving the O(k53)-vertex kernel of Fomin et al. (2013) [11]. We start from a constant-approximation solution and study its interaction with other vertices, which induce a unit interval graph. We partition vertices of this unit interval graph into cliques in a naive way, and pick a small number of representatives from each of them. Our constructive proof for the correctness of our algorithm, using interval models, greatly simplifies the “destructive” proofs, based on destroying forbidden structures, for similar problems in literature. Our algorithm can be implemented in O(mn+n2) time, where n and m denote respectively the numbers of vertices and edges of the input graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 109-121
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 109-121
نویسندگان
Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, Jianxin Wang,