On spanning 2-trees in a graph (Q1356500): Difference between revisions

The paper presents an approximation algorithm for finding a minimum-weight spanning 2-tree in a weighted complete graph. The asymptotic performance ratio is less than or equal to 2 when the edge weights satisfy the triangle equality, and at most \((3+ 4\sqrt 3)/6\approx 1.655\) when the graph is a complete Euclidean graph on a set of points in the plane.