Reductions to 1–matching polyhedra

DOI10.1002/net.3230130403zbMath0525.90068OpenAlexW2052855790WikidataQ126263460 ScholiaQ126263460MaRDI QIDQ3039038

William H. Cunningham, Jan Green-Krótki, Jack Edmonds, Julián Aráoz

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230130403

zbMATH Keywords

bidirected graphpolyhedral characterizationperfect b-matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Polytopes and polyhedra (52Bxx)

Related Items

Linear and combinatorial sharing problems ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ Forest covers and a polyhedral intersection theorem ⋮ On the transportation problem with market choice ⋮ On cycle cones and polyhedra ⋮ Privatized rural postman problems ⋮ Path hitting in acyclic graphs ⋮ On dual integrality in matching problems ⋮ Solving the prize-collecting rural postman problem

Cites Work

• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices