Lower bounds for testing Euclidean Minimum Spanning Trees.

Oren Ben-Zwi Oded Lachish Ilan Newman

Published in: Inf. Process. Lett. (2007)

Keyphrases

minimum spanning trees
lower bound
upper bound
minimum spanning tree
spanning tree
euclidean distance
neighborhood graph
objective function
np hard
worst case
euclidean space
optimal solution
high dimensional
edge weights