On the Longest Spanning Tree with Neighborhoods

Abstract

We study a maximization problem for geometric network design. Given a set of $n$ compact neighborhoods in ${\mathbb{R}}^d$, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here we give an approximation algorithm with ratio $0.511$, which represents the first, albeit small, improvement beyond $1/2$. While we suspect that the problem is NP-hard already in the plane, this issue remains open.

12 pages, 4 figures. Section 2 is split into three subsections; more technical details are provided in section 3

References in corpus (1)

• Minimum Spanning trees with Neighborhoods