کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331049 | 686440 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A linear time algorithm for optimal k-hop dominating set of a tree
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A linear time algorithm for optimal k-hop dominating set of a tree A linear time algorithm for optimal k-hop dominating set of a tree](/preview/png/10331049.png)
چکیده انگلیسی
We give a linear time algorithm to compute an optimal (minimum) k-hop dominating set D of a tree T for kâ¥1. This extends the previous result for an optimal 1-dominating set for trees. We use a rooted form T¯ of T, with an arbitrary node selected as the root, to direct the search for nodes of D in a bottom-up fashion. The decision whether to include a node x in D or not is based on the subtree of T¯ at x. Optimal k-hop dominating sets have many important practical applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 197-202
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 197-202
نویسندگان
Sukhamay Kundu, Subhashis Majumder,