2026-07-25T01:47:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15440 2024-03-06T10:55:17Z ddc:004 open_access

Approximating Longest Spanning Tree with Neighborhoods Biniaz, Ahmad Euclidean maximum spanning tree spanning tree with neighborhoods approximation algorithms We study the following maximization problem in the Euclidean plane: Given a collection of neighborhoods (polygonal regions) in the plane, the goal is to select a point in each neighborhood so that the longest spanning tree on selected points has maximum length. It is not known whether or not this problem is NP-hard. We present an approximation algorithm with ratio 0.548 for this problem. This improves the previous best known ratio of 0.511. The presented algorithm takes linear time after computing a diameter. Even though our algorithm itself is fairly simple, its analysis is rather involved. In some part we deal with a minimization problem with multiple variables. We use a sequence of geometric transformations to reduce the number of variables and simplify the analysis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.7 urn:nbn:de:0030-drops-154401 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode