Low-Degree Spanning Trees of Small Weight

Details Low-Degree Spanning Trees of Small Weight Low-Degree Spanning Trees of Small Weight

2002-05-18

arxiv.org/abs/cs/0205043v1

SIAM J. Computing 25(2):355-368 (1996)

Computer Science

Data Structures and Algorithms

conference version in Symposium on Theory of Computing (1994)

Scientific paper

The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-known Christofides algorithm provides a 1.5-approximation algorithm (assuming the edge weights satisfy the triangle inequality). In 1984, Christos Papadimitriou and Umesh Vazirani posed the challenge of finding an algorithm with performance guarantee less than 2 for Euclidean graphs (points in R^n) and d > 2. This paper gives the first answer to that challenge, presenting an algorithm to compute a degree-3 spanning tree of cost at most 5/3 times the MST. For points in the plane, the ratio improves to 3/2 and the algorithm can also find a degree-4 spanning tree of cost at most 5/4 times the MST.

Affiliated with

Also associated with

No associations

Rating

Low-Degree Spanning Trees of Small Weight does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Low-Degree Spanning Trees of Small Weight, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-Degree Spanning Trees of Small Weight will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599171