License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.14
URN: urn:nbn:de:0030-drops-122616
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12261/
Go to the corresponding LIPIcs Volume Portal

Biniaz, Ahmad ; Bose, Prosenjit ; Lubiw, Anna ; Maheshwari, Anil

Bounded-Angle Minimum Spanning Trees

pdf-format:
LIPIcs-SWAT-2020-14.pdf (1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{biniaz_et_al:LIPIcs:2020:12261,
  author =	{Ahmad Biniaz and Prosenjit Bose and Anna Lubiw and Anil Maheshwari},
  title =	{{Bounded-Angle Minimum Spanning Trees}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12261},
  URN =		{urn:nbn:de:0030-drops-122616},
  doi =		{10.4230/LIPIcs.SWAT.2020.14},
  annote =	{Keywords: bounded-angle MST, directional antenna, approximation algorithms}
}

Keywords: bounded-angle MST, directional antenna, approximation algorithms
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI