• SIAM Journal on Computing 25(2):355-368(1996); STOC'94

  With Samir Khuller and Balaji Raghavachari
  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).
  
  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\) [1984]. 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.

  Journal version of [1994].

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.