A compact linear program for testing optimality of perfect matchings.

DOI10.1016/S0167-6377(03)00052-XMaRDI QIDQ1412705zbMATH OpenFDO

Authors P. Ventura, Friedrich Eisenbrand

Publication date 25 November 2003

Published in Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

Matchingcompact linear programming

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Discrete location and assignment (90B80)

Recommendations

• Polynomial size linear programs for problems in \textsc{P}
• Reducing Matching to Polynomial Size Linear Programming
• On the inverse problem of linear programming and its application to minimum weight perfect \(k\)-matching
• Solving matching problems with linear programming

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Expressing combinatorial optimization problems by linear programs
• Graph Theory and Integer Programming
• Matching, Euler tours and the Chinese postman
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On cuts and matchings in planar graphs
• On the core of network synthesis games
• Paths, Trees, and Flowers
• Reducing Matching to Polynomial Size Linear Programming
• Short proofs on the matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(7)

• Learning in combinatorial optimization: what and how to explore
• Symmetry Matters for Sizes of Extended Formulations
• Birkhoff-von Neumann graphs that are PM-compact
• Extended formulations for radial cones
• Reducing Matching to Polynomial Size Linear Programming
• Compact linear programs for 2SAT
• Polynomial size linear programs for problems in \textsc{P}

This page was built for publication: A compact linear program for testing optimality of perfect matchings.

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