A separation algorithm for the matchable set polytope

DOI10.1007/BF01581694zbMath0819.90120OpenAlexW2032311650MaRDI QIDQ1334957

Jan Green-Krótki, William H. Cunningham

Publication date: 26 September 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581694

zbMATH Keywords

augmenting pathseparation algorithmmatchable set of a graphmin-max theorem characterizingpolynomial-time combinatorial algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items (4)

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ Matchability and \(k\)-maximal matchings ⋮ Perfectly matchable subgraph problem on a bipartite graph ⋮ The optimal path-matching problem

Cites Work

• On T-joins and odd factors
• The perfectly matchable subgraph polytope of an arbitrary graph
• An application of simultaneous diophantine approximation in combinatorial optimization
• The ellipsoid method and its consequences in combinatorial optimization
• \(b\)-matching degree-sequence polyhedra
• Odd Minimum Cut-Sets and b-Matchings
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item

This page was built for publication: A separation algorithm for the matchable set polytope