On matroid parity and matching polytopes

DOI10.1016/J.DAM.2020.03.049MaRDI QIDQ777400zbMATH OpenOpenAlexFDO

Authors Konstantinos Kaparis, Adam N. Letchford, Ioannis Mourtos

Publication date 7 July 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://eprints.lancs.ac.uk/id/eprint/142783/1/DA11382_R1.pdf

zbMATH Keywords

polyhedral combinatoricsmatroid matchingmatroid parity

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• On the generalization of the matroid parity problem
• On the graphic matroid parity problem
• Matching, matroids, and extensions
• Matchings and \(\Delta\)-matroids
• scientific article; zbMATH DE number 1757951
• scientific article; zbMATH DE number 3150
• Structural properties of matroid matchings
• Note on a matroid with parity condition
• Matching as the Intersection of Matroids
• Perfect matching and polymatroids

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 1354128 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3361920 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• An algorithm for weighted fractional matroid matching
• An augmenting path algorithm for linear matroid parity
• Combinatorial theory.
• Complexity of Matroid Property Algorithms
• Edmonds polytopes and a hierarchy of combinatorial problems
• Fractional matroid matchings
• Matching theory
• Matroid matching and some applications
• Matroid matching: the power of local search
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• Outline of an algorithm for integer solutions to linear programs
• Paths, Trees, and Flowers
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

Cited in

(7)

• Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
• The parity problem of polymatroids without double circuits
• scientific article; zbMATH DE number 4174676 (Why is no real title available?)
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• A note on the separation problem for the matching matroid
• Structural properties of matroid matchings
• Note on a matroid with parity condition

This page was built for publication: On matroid parity and matching polytopes

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