I am currently looking into solving TSP using Branch and Bound method. In the book by Wayne and Winston, they have solved each subproblem (i.e. tree nodes) using Hungarian algorithm.
Using the lecture at this link, I learned that in order to implement Hungarian algorithm, we should be looking for M-augmenting paths, where M defines an arbitrary matching on the bipartite graph. In my knowledge, augmenting path satisfies following conditions;
a.) alternating path, and
b.) first and last vertices being unmarked.
When we look at augmenting paths for TSP, do we need to make sure that the path covers all cities? Or can we stop augmenting once above two conditions in a) and b) are satisfied? Second, is it okay to repeat a city in the augmenting path keeping above conditions satisfied?
