کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949939 | 1440207 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient domination through eigenvalues
ترجمه فارسی عنوان
تسلط کارآمد از طریق ارزشهای خاص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The paper begins with a new characterization of (k,Ï)-regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a (0,Ï)-regular set. When Ï=1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP-complete. If â1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it does not work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 54-62
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 54-62
نویسندگان
Domingos M. Cardoso, Vadim V. Lozin, Carlos J. Luz, Maria F. Pacheco,