کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
411594 679578 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding graph minimum stable set and core via semi-tensor product approach
ترجمه فارسی عنوان
پیدا کردن گراف حداقل مجموعه پایدار و هسته با استفاده از روش نیمه تانسور محصول
کلمات کلیدی
نمودار، حداقل مجموعه پایدار، هسته گراف، محصول نیمه انسانی، شبکه های پیچیده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی


• Use STP to study the minimum stable set and core of graph.
• An algorithm is established to find all the externally stable sets.
• Necessary and sufficient condition for absolutely minimum externally stable set.
• An algorithm is established to find all the graph cores via semi-tensor product.
• Examples illustrate the results/algorithms very well.

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Neurocomputing - Volume 174, Part B, 22 January 2016, Pages 588–596
نویسندگان
, , , , ,