This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Zhang, F. Search for Related Content

A Separation Algorithm for b-Matching Degree-Sequence Polyhedra

Department of Computing, The Hong Kong Polytechnic University, Kowloon, Hong Kong
csfzhang(comp.polyu.edu.hk

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.

Key Words: Combinatorial optimization; b-matching; degree sequence; polyhedron combinatorics
History: Received: May 22, 2002; revision received: September 12, 2002;