1
$\begingroup$

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.

$\endgroup$

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.