2026-07-24T09:31:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15823 2024-03-06T10:56:16Z ddc:004 open_access

A 10-Approximation of the π/2-MST Biniaz, Ahmad Daliri, Majid Moradpour, Amir Hossein Euclidean spanning trees approximation algorithms bounded-angle visibility 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz and Majid Daliri and Amir Hossein Moradpour 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.13 urn:nbn:de:0030-drops-158232 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode