کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903509 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weighted upper domination number
ترجمه فارسی عنوان
شماره سلطه بالایی وزن
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The cardinality of a maximum minimal dominating set of a graph is called its upper domination number. The problem of computing this number is generally NP-hard but can be solved in polynomial time in some restricted graph classes. In this work, we consider the complexity and approximability of the weighted version of the problem in two special graph classes: planar bipartite, split. We also provide an inapproximability result for an unweighted version of this problem in regular graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 171-176
نویسندگان
, ,