کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6420693 1631798 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Resolving-power dominating sets
ترجمه فارسی عنوان
مجموعه های حاکم بر حل مسئله قدرت
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
چکیده انگلیسی


- A new concept resolving-power dominating sets is introduced.
- The problem is proven to be NP-complete.
- The resolving power domination number is studied for trees.

For a graph G(V,E) that models a facility or a multi-processor network, detection devices can be placed at vertices so as to identify the location of an intruder such as a thief or fire or saboteur or a faulty processor. Resolving-power dominating sets are of interest in electric networks when the latter helps in the detection of an intruder/fault at a vertex. We define a set S⊆V to be a resolving-power dominating set of G if it is resolving as well as a power-dominating set. The minimum cardinality of S is called resolving-power domination number. In this paper, we show that the problem is NP-complete for arbitrary graphs and that it remains NP-complete even when restricted to bipartite graphs. We provide lower bounds for the resolving-power domination number for trees and identify classes of trees that attain the lower bound. We also solve the problem for complete binary trees.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 256, 1 April 2015, Pages 778-785
نویسندگان
, , , ,