2026-07-23T08:16:16Z https://drops.dagstuhl.de/oai

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

Planar Bichromatic Bottleneck Spanning Trees Abu-Affash, A. Karim Bhore, Sujoy Carmi, Paz Mitchell, Joseph S. B. Approximation Algorithms Bottleneck Spanning Tree NP-Hardness Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a geometric spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Our main contribution is a polynomial-time (8√2)-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√2 λ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik A. Karim Abu-Affash and Sujoy Bhore and Paz Carmi and Joseph S. B. Mitchell 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.1 urn:nbn:de:0030-drops-128670 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.1 eng https://creativecommons.org/licenses/by/3.0/legalcode