A note on matchings and separability

DOI10.1016/0166-218X(85)90013-7MaRDI QIDQ802467zbMATH OpenFDO

Authors William Cook

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(85)90013-7

zbMATH Keywords

independence systemsmatching polytopeminimal totally dual integral systemsseparability

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Integer programming (90C10)

Review text

It is observed that minimal totally dual integral systems for a class of independence systems are closely related to a type of separability. This observation is used to give a short proof, using Edmond's matching polytope theorem, of a theorem of Cunningham and Marsh which gives a description of the minimal totally dual integral defining system for the matching polytope and also to show the relationship between that result and a theorem of F. R. Giles.

Recommendations

• Total dual integrality of matching forest constraints
• Linear Systems for Constrained Matching Problems
• When is the matching polytope box-totally dual integral?
• A note on the separation problem for the matching matroid
• On dual integrality in matching problems

Cites work

• A Minimal Totally Dual Integral Defining System for the b-Matching Polyhedron
• Dual integrality in b-matching problems
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 3862931 (Why is no real title available?)
• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 3904605 (Why is no real title available?)
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3499169 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3598496 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Linear Systems for Constrained Matching Problems
• Local Unimodularity in the Matching Polytope
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• On total dual integrality
• Short proofs on the matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization
• Total dual integrality and b-matchings
• Total dual integrality and integer polyhedra

Cited in

(6)

• Structural properties of matroid matchings
• A theorem on the principal structure for independent matchings
• Linear Systems for Constrained Matching Problems
• When is the matching polytope box-totally dual integral?
• Total dual integrality of matching forest constraints
• A note on Banach's match box problem

This page was built for publication: A note on matchings and separability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802467)