کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874721 | 1441190 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dual power assignment via second Hamiltonian cycle
ترجمه فارسی عنوان
تقسیم قدرت دوگانه از طریق چرخه همیلتون دوم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم تقریبی، تقسیم قدرت، هندسه محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from Ï26â136+ϵâ1.617 to 117â1.571. Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 93, May 2018, Pages 41-53
Journal: Journal of Computer and System Sciences - Volume 93, May 2018, Pages 41-53
نویسندگان
A. Karim Abu-Affash, Paz Carmi, Anat Parush Tzur,