کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431299 | 688499 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dominating induced matchings in graphs without a skew star
ترجمه فارسی عنوان
غلبه بر ماتریس القا شده در نمودارها بدون ستاره مبهم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
غلبه بر تطبیق القایی، لبه کارآزموده غلبه بر مجموعه، الگوریتم زمان چندجملهای، عرض کلاسی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the problem of determining whether a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general graphs, but it can be solved in polynomial time for graphs in some special classes, such as weakly chordal, P7P7-free or claw-free graphs. In the present paper we extend the polynomial-time solvability of the problem from claw-free graphs to graphs without a skew star, where a skew star is a tree with exactly three vertices of degree 1 being of distance 1,2,31,2,3 from the only vertex of degree 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 45–55
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 45–55
نویسندگان
Nicholas Korpelainen, Vadim V. Lozin, Christopher Purcell,