. Initialise the stack to being empty. Repeat Set and . For all , push onto the stack. While the stack is nonempty: Pop off the stack and let . If is even then for each such that , push onto the stack if: , or and is a tour (Hamiltonicity check) else ( is odd): If , , and is a tour (Hamiltonicity check) then let and . For each such that and , push onto the stack. End if. Let be the top element on the stack (peek, not pop). If then if then set (update current tour) and clear the stack. else if then pop all elements off the stack that have end if end if end while until . Return The length of the alternating trails considered are thus not explicitly bounded, but beyond the backtracking depth no more than one way of extending the current trail is considered, which in principle stops those explorations from raising the exponent in the runtime complexity. Limitations The closed alternating trails found by the above method are all connected, but the symmetric difference of two tours need not be, so in general this method of alternating trails cannot explore the full neighbourhood of a trail . The literature on the Lin–Kernighan heuristic uses the term sequential exchanges for those that are described by a single alternating trail. The smallest non-sequential exchange would however replace 4 edges and consist of two cycles of 4 edges each (2 edges added, 2 removed), so it is long compared to the typical Lin–Kernighan exchange, and there are few of these compared to the full set of 4-edge exchanges. In at least one implementation by Lin & Kernighan there was an extra final step considering such non-sequential exchanges of 4 edges before declaring a tour locally optimal, which would mean the tours produced are 4-opt unless one introduces further constraints on the search (which Lin and Kernighan in fact did). The literature is vague on exactly what is included in the Lin–Kernighan heuristic proper, and what constitutes further refinements. For the asymmetric TSP, the idea of using positive gain alternating trails to find favourable exchanges is less useful, because there are fewer ways in which pieces of a tour can be rearranged to yield new tours when one may not reverse the orientation of a piece. Two pieces can only be patched together to