The Complexity of Maximizing the MST-ratio
The Complexity of Maximizing the MST-ratio
Given a finite set of red and blue points in $\mathbb{R}^d$, the MST-ratio is the combined length of the Euclidean minimum spanning trees of red points and of blue points divided by the length of the Euclidean minimum spanning tree of the union of them. The maximum MST-ratio of a …