Planar Realization
The realization problem for Euclidean minimum spanning trees is stated as follows: Given a tree T = (V, E), find a location D(u) for each vertex u ∈ V so that T is a minimum spanning tree of D(u): u ∈ V, or determine that no such locations exist. Testing of the existence of a realization in the plane is NP-hard.
Read more about this topic: Euclidean Minimum Spanning Tree
Famous quotes containing the word realization:
“Among all the modernized aspects of the most luxurious of industries, the model, a vestige of voluptuous barbarianism, is like some plunder-laden prey. She is the object of unbridled regard, a living bait, the passive realization of an ideal.... No other female occupation contains such potent impulses to moral disintegration as this one, applying as it does the outward signs of riches to a poor and beautiful girl.”
—Colette [Sidonie Gabrielle Colette] (1873–1954)