Revision as of 05:40, 12 August 2010 edit 203.244.221.1 (talk) →Steiner ratio ← Previous edit		Revision as of 05:44, 12 August 2010 edit undo 203.244.221.1 (talk) →Steiner ratio Next edit →
Line 62: In the metric Steiner tree problems, the Steiner ratio is 2. Therefore an algorithm that finds a minimum spanning tree is a polynomial-time factor-2 [[approximation algorithm]] for the metric Steiner tree problem. In the Euclidean Steiner tree problem, the Steiner ratio is \sqrt{3}<//<math>2~~</math>~~. ==Notes==

Steiner tree problem: Difference between revisions