کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420185 683902 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parameterized complexity of generalized domination problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Parameterized complexity of generalized domination problems
چکیده انگلیسی

Given two sets σ,ρσ,ρ of non-negative integers, a set SS of vertices of a graph GG is (σ,ρ)(σ,ρ)-dominating   if |S∩N(v)|∈σ|S∩N(v)|∈σ for every vertex v∈Sv∈S, and |S∩N(v)|∈ρ|S∩N(v)|∈ρ for every v∉Sv∉S. This concept, introduced by Telle in 1990’s, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of (σ,ρ)(σ,ρ)-domination in this general setting. Among other results, we show that the existence of a (σ,ρ)(σ,ρ)-dominating set of size kk (and at most kk) are W[1]-complete problems (when parameterized by kk) for any pair of finite sets σσ and ρρ. We further present results on dual parameterization by n−kn−k, and results on certain infinite sets (in particular for σ,ρσ,ρ being the sets of even and odd integers).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 780–792
نویسندگان
, , ,