Том 20, номер 1, 2013 г., Стр. 12-27
УДК 519.8
Ерзин А. И., Плотников Р. В., Шамардин Ю. В.
О некоторых полиномиально разрешимых случаях и приближённых алгоритмах
для задачи построения оптимального коммуникационного дерева
Аннотация:
В произвольном неориентированном$n$ -вершинном графе с неотрицательными весами рёбер требуется построить остовное дерево, в котором сумма по всем вершинам максимальных весов инцидентных вершине рёбер минимальна. Найдены частные случаи полиномиальной разрешимости. Показано, что минимальный остов, веса рёбер которого принадлежат отрезку$[a,b]$ , является$\bigl(2-\frac{2a}{a+b+2b/(n-2)}\bigr)$ -приближённым решением и задача построения 1,00048-приближённого решения NP-трудна. Предложен эвристический полиномиальный алгоритм, и осуществлён его апостериорный анализ.
Табл. 4, ил. 4, библиогр. 9.
Ключевые слова: беспроводная коммуникационная сеть, остовное дерево, приближённый алгоритм.
Ерзин Адиль Ильясович 1,2
Плотников Роман Викторович 2
Шамардин Юрий Владиславович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: adilerzin@math.nsc.ru, nomad87@ngs.ru, orlab@math.nsc.ru
Статья поступила 17 января 2012 г.
Исправленный вариант — 28 марта 2012 г.
Литература
[1] Астраков С. Н., Ерзин А. И., Залюбовский В. В. Сенсорные сети и покрытие плоскости кругами // Дискрет. анализ и исслед. операций. - 2009. - T. 16, № 3. - C. 3–19.
[2] Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. - М.: Физматгиз, 1958. - 365 с.
[3] Althaus E., et al. Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks // Wireless Networks. - 2006. - Vol. 12, N 3. - P. 287–299.
[4] Berman P., Karpinski M. On some tighter inapproximability results // Electron. Colloquium Computational Complexity (ECCC). - 1998. - TR98–065.
[5] Clementi A. E. F., Penna P., Silvestri R. On the power assignment problem in radio networks // Electron. Colloquium Computational Complexity (ECCC). - 2000. - TR00–054.
[6] Carmi P., Katz M. L. Power assignment in radio networks with two power levels // Algorithmica. - 2007. - N 47. - P. 183–201.
[7] Diane M., Plesnik J. An integer programming formulation of the Steiner problem in graphs // Math. Methods Oper. Res. - 1993. - N 37. - P. 107–111.
[8] Kershner R. The number of circles covering a set // Amer. J. Math. - 1939. - Vol. 61, N 3. - P. 665–671.
[9] Kirousis L. M., Kranakis E., Krizanc D., Pelc A. Power consumption in packet radio networks // Theor. Comput. Sci. - 2000. - N 243. - P. 289–305.
[10] Pottie G. J., Kaiser W. J. Wireless integrated network sensors // Commun. ACM. - 2000. - Vol. 43, N 5. - P. 51–58.
[11] Tóth F. G. Covering the plane with two kinds of circles // Discrete Comput. Geometry. - 1995. - Vol. 13, N 3. - P. 445–457.
[12] Wu J., Dai F. Virtual backbone construction in MANETs using adjustable transmission ranges // IEEE Trans. Mobile Comput. - 2006. - Vol. 5, N 9. - P. 1188–1200.
[13] Wu J., Yang S. Energy-efficient node scheduling models in sensor networks with adjustable ranges // Int. J. Found. Comput. Sci. - 2005. - Vol. 16, N 1. - P. 3–17.
[14] Zhang H., Hou J. C. Maintaining sensing coverage and connectivity in large sensor networks // Ad Hoc & Sensor Wireless Networks. - 2005. - Vol. 1, N 1–2. - P. 89–124.
