Portal de Periódicos da CAPES

Odd Minimum Cut-Sets and b -Matchings

1982; Institute for Operations Research and the Management Sciences; Volume: 7; Issue: 1 Linguagem: Inglês

10.1287/moor.7.1.67

1526-5471

Manfred Padberg, M. R. Rao,

Vehicle Routing Optimization Methods

We show that the determination of a minimum cut-set of odd cardinality in a graph with even and odd vertices can be dealt with by a minor modification of the polynomially bounded algorithm of Gomory and Hu for multi-terminal networks. We connect this problem to the problem of identifying a matching (or blossom) constraint that chops off a point which is not contained in the convex hull of matchings or proving that no such inequality exists. Both the b-matching problems without and with upper bounds are considered. We discuss how the results of this paper can be used in conjunction with commercial LP packages lo solve b-matching problems.