کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871970 | 684128 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of total outer-connected domination problem in graphs
ترجمه فارسی عنوان
پیچیدگی کل مسئله سلطه بیرونی در نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set DâV is called a total dominating set of a graph G=(V,E), if for all vâV, |NG(v)â©D|â¥1. A total dominating set D of G=(V,E) is called a total outer-connected dominating set if G[VâD] is connected. The Minimum Total Outer-connected Domination problem for a graph G=(V,E) is to find a total outer-connected dominating set of minimum cardinality. The Total Outer-connected Domination Decision problem, the decision version of the Minimum Total Outer-connected Domination problem, is known to be NP-complete for general graphs. In this paper, we strengthen this NP-completeness result by showing that the Total Outer-connected Domination Decision problem remains NP-complete for chordal graphs, split graphs, and doubly chordal graphs. We prove that the Total Outer-connected Domination Decision problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for computing the total outer-connected domination number, the cardinality of a minimum total outer-connected dominating set, of a tree. We prove that the Minimum Total Outer-connected Domination problem cannot be approximated within a factor of (1âε)ln|V| for any ε>0, unless NP â DTIME (|V|O(loglog|V|)). Finally, we show that the Minimum Total Outer-connected Domination problem is APX-complete for bounded degree graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 110-122
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 110-122
نویسندگان
B.S. Panda, Arti Pandey,