کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874253 686948 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of {k}-domination and k-tuple domination in graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of {k}-domination and k-tuple domination in graphs
چکیده انگلیسی
We consider two types of graph domination-{k}-domination and k-tuple domination, for a fixed positive integer k-and provide new NP-complete as well as polynomial time solvable instances for their related decision problems. Regarding NP-completeness results, we solve the complexity of the {k}-domination problem on split graphs, chordal bipartite graphs and planar graphs, left open in 2008. On the other hand, by exploiting Courcelle's results on Monadic Second Order Logic, we obtain that both problems are polynomial time solvable for graphs with clique-width bounded by a constant. In addition, we give an alternative proof for the linearity of these problems on strongly chordal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6–8, June–August 2015, Pages 556-561
نویسندگان
, , ,