= Degree branching with a one-tree bound
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.
Back to article page
