If a minimum one-tree is not a tour, some vertex has degree greater than two, since there are equally many edges and vertices. Every tour must omit at least one of its incident selected edges. Partition tours by the first omitted edge in an ordered list, forcing all preceding listed edges and forbidding that edge. These disjoint children cover all tours. Recompute the constrained one-tree lower bound in each child and compare it with the incumbent solution to prune.
Articles by others on the same topic
There are currently no matching articles.