Separating from the dominant of the spanning tree polytope

Abstract

We study the separation problem for the partition inequalities that define the dominant of the spanning tree polytope of a graph G = (V, E). We show that a most violated inequality can be found by solving at most |V| maximum flow problems. Cunningham (1985) had solved this as a sequence of |E| maximum flow problems. © 1992.