A Algorithm Pseudo Code for Approximating of Maximal Independent Set in the Unit Disc Graph
The unit disk graph is used to model a wireless sensor network when all sensors have the same communication radius. Hence, the following two optimization problems have been investigated by the researchers: maximal independent set in the network and minimal network dominating set. Since these problems are Np-hard, several algorithms have been presented for their approximation. In this paper, we have presented a honeycomb graph and algorithmic matrix methods for approximating the maximal independent set in the network. Finally, we have confirmed the validity of the algorithm and its complexity and studied it with a numerical example. Keywords: Wireless network, Independent set, Dominating set, Algorithm, Honeycomb network E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066. N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.