A separation algorithm for b-matching degree-sequence polyhedra

A separation algorithm for b-matching degree-sequence polyhedra

0.00 Avg rating0 Votes
Article ID: iaor2004857
Country: United States
Volume: 28
Issue: 1
Start Page Number: 92
End Page Number: 102
Publication Date: Feb 2003
Journal: Mathematics of Operations Research
Authors:
Keywords: game theory
Abstract:

A b-matching of a graph is an assignment of non-negative integers to edges such that the sum at each node is at most a given bound. Its degree sequence is the vector whose components are the sums at each node. A linear-inequality description for the convex hull of degree sequences of b-matchings of a graph was found by Cunningham and Green-Krótki. This paper presents a polynomial-time combinatorial algorithm that either certifies a given vector as a member of the polyhedron or finds a valid inequality that is violated by the vector.

Reviews

Required fields are marked *. Your email address will not be published.