Biniaz, Ahmad
[Verfasser:in];
Daliri, Majid
[Verfasser:in];
Moradpour, Amir Hossein
[Verfasser:in]
;
Ahmad Biniaz and Majid Daliri and Amir Hossein Moradpour
[Mitwirkende:r]
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Bounded-angle spanning trees of points in the plane have received considerable attention in the context of wireless networks with directional antennas. For a point set P in the plane and an angle α, an α-spanning tree (α-ST) 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. The α-minimum spanning tree (α-MST) problem asks for an α-ST of minimum total edge length. The seminal work of Anscher and Katz (ICALP 2014) shows the NP-hardness of the α-MST problem for α = 2π/3, π and presents approximation algorithms for α = π/2, 2π/3, π. In this paper we study the α-MST problem for α = π/2 which is also known to be NP-hard. We present a 10-approximation algorithm for this problem. This improves the previous best known approximation ratio of 16.