کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949672 | 1440198 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the barrier graph of an arrangement of ray sensors
ترجمه فارسی عنوان
بر روی مانع گراف از ترتیب سنسورهای اشعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شبکه حسگر بی سیم، نمودار مانع،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The main result of this paper is a rigidity theorem on the structure of barrier graphs that results from constraints imposed by the geometry of the network. This allows us to show that almost all bipartite graphs are not barrier graphs, despite the fact that various classes of bipartite graphs, including trees, cycles of even length, and Km,n are barrier graphs. Furthermore, vertex cover of a barrier graph corresponds to a set of sensors whose removal allows a clear path from α to β. While all bipartite graphs with small vertex covers are barrier graphs (a fact we prove for sizes less than 4), the rigidity property also implies that graphs with vertex covers bigger than a certain constant are not barrier graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 225, 10 July 2017, Pages 11-21
Journal: Discrete Applied Mathematics - Volume 225, 10 July 2017, Pages 11-21
نویسندگان
Kirk Boyer, Paul Horn, Mario A. Lopez,