کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431299 688499 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dominating induced matchings in graphs without a skew star
ترجمه فارسی عنوان
غلبه بر ماتریس القا شده در نمودارها بدون ستاره مبهم
کلمات کلیدی
غلبه بر تطبیق القایی، لبه کارآزموده غلبه بر مجموعه، الگوریتم زمان چندجملهای، عرض کلاسی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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