Reducing Matching to Polynomial Size Linear Programming

DOI10.1137/0803035zbMath0806.90100OpenAlexW1978037005MaRDI QIDQ4277507

Francisco Barahona

Publication date: 7 February 1994

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0803035

zbMATH Keywords

matchingpolynomial algorithmsystems of linear inequalitiesChinese postmancompact linear programminimum mean cycle problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

A compact linear program for testing optimality of perfect matchings. ⋮ Extended formulations in combinatorial optimization ⋮ On cuts and matchings in planar graphs ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ Extended formulations in combinatorial optimization ⋮ Minimum mean cycle problem in bidirected and skew-symmetric graphs

This page was built for publication: Reducing Matching to Polynomial Size Linear Programming