Matching: A well-solved class of integer linear programs

DOI10.1007/3-540-36478-1_3MaRDI QIDQ4414633zbMATH OpenFDO

Authors Jack Edmonds, Ellis L. Johnson

Publication date 25 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2570/25700027.htm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Reducing Matching to Polynomial Size Linear Programming
• A new algorithm for general matching problems using network flow subproblems
• Solving matching problems with linear programming
• scientific article; zbMATH DE number 5211512
• scientific article; zbMATH DE number 795216

Cited in

(39)

• Local unimodularity of matrix-vector pairs
• A primal dual integer programming algorithm
• Matching problems in selective assembly operations
• Computing a consensus trajectory in a vehicular network
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• Gain-line graphs via \(G\)-phases and group representations
• On dual integrality in matching problems
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
• Optimization with binet matrices
• Edmonds polytopes and a hierarchy of combinatorial problems
• A greedy algorithm for the social golfer and the Oberwolfach problem
• A mathematical view of matching food and wine
• On eigenspaces of some compound signed graphs
• The disjunctive procedure on the matching problem
• Approximating the Minimum Tour Cover with a Compact Linear Program
• scientific article; zbMATH DE number 3913665 (Why is no real title available?)
• Intermediate feasibility in 0–1 integer linear systems
• Linear Systems for Constrained Matching Problems
• Theorem with applications in coding and matching problems
• scientific article; zbMATH DE number 59833 (Why is no real title available?)
• Matching problems with knapsack side constraints. A computational study
• Reducing Matching to Polynomial Size Linear Programming
• Using matching to detect infeasibility of some integer programs
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Switching graphs
• Total graph of a signed graph
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• On the metric \(s\)-\(t\) path traveling salesman problem
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Matching 2-lattice polyhedra: Finding a maximum vector
• Convex quadratic programming approach
• Graph covering using bounded size subgraphs
• AlfaPang: alignment free algorithm for pangenome graph construction
• Computational complexity of covering multigraphs with semi-edges: small cases
• Gain total graphs and their spectra via G-phases and group representations
• The complexity of decomposing a graph into a matching and a bounded linear forest
• Hierarchical \(b\)-matching
• Structural analysis of a fractional matching problem

This page was built for publication: Matching: A well-solved class of integer linear programs

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