In the STSP i know the 1-tree relaxation procedure:

  1. Determine a minimum cost spanning tree on nodes $\{{2, . . . , n}\}$ by using a greedy algorithm (Kruskal, Prim,...),
  2. select two edges incident in node 1 with smallest cost.

This offer me a lower bound for my problem,in my homework is asked me to apply the 2-tree relaxation,i don't find some explanation on web,and i suppose that i have to find a minimum cost spanning tree on nodes $\{3,..,n\}$ and after select some incident edges on nodes $\{1,2\}$,but i'm not able to understand in which way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.