文章基本信息

标题：Bounded-Angle Minimum Spanning Trees
本地全文：下载
作者：Ahmad Biniaz ; Prosenjit Bose ; Anna Lubiw 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：14:1-14:22
DOI：10.4230/LIPIcs.SWAT.2020.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let Î± be an angle. An Î±-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p â^^ P lie in a wedge of angle Î± centered at p. We study the following closely related problems for Î± = 120 degrees (however, our approximation ratios hold for any Î± â©¾ 120 degrees). 1) The Î±-minimum spanning tree problem asks for an Î±-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an Î±-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. 2) To examine what is possible with non-uniform wedge angles, we define an Ì.Î±-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle Î±. We present an algorithm to find an Ì.Î±-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle Î±. Our algorithm runs in linear time after computing the MST.
关键词：bounded-angle MST; directional antenna; approximation algorithms