کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874156 | 1441026 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum matching and kernelization of edge dominating set
ترجمه فارسی عنوان
حداکثر تطبیق و کرنل لبه غالب مجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The edge dominating set problem is NP-hard, even when the graph is restricted to planar or bipartite graphs with maximum degree three. In this paper, we prove that in every graph where each vertex is incident to at most one vertex of degree one, the cardinality of maximum matching is at least 2|V|/(3+maxâ¡(3,Î(G))). Using the aforementioned result together with a simple reduction rule, we obtain a linear kernel of size 6k for the edge dominating set problem for graphs with maximum degree three.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 136, August 2018, Pages 21-24
Journal: Information Processing Letters - Volume 136, August 2018, Pages 21-24
نویسندگان
Hang Gao, Wenyu Gao,