Solving the linear matroid parity problem as a sequence of matroid intersection problems

DOI10.1007/BF01580854MaRDI QIDQ1813836zbMATH OpenOpenAlexDBLPWikidataFDO

Authors James B. Orlin, John H. Vande Vate

Publication date 25 June 1992

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

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

zbMATH Keywords

duality resultsgraphic matching problemslinear matroid parity problem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A Fast, Simpler Algorithm for the Matroid Parity Problem
• A weighted linear matroid parity algorithm
• An augmenting path algorithm for linear matroid parity
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems

Cites work

• An augmenting path algorithm for linear matroid parity
• An extension of matching theory
• Complexity of Matroid Property Algorithms
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3646634 (Why is no real title available?)
• scientific article; zbMATH DE number 3703542 (Why is no real title available?)
• scientific article; zbMATH DE number 3499169 (Why is no real title available?)
• Matroid intersection algorithms
• Matroid matching and some applications
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• Multi-Terminal Network Flows
• Optimal Sequencing of Two Equivalent Processors
• Optimum matching forests I: Special weights
• Paths, Trees, and Flowers
• Perfect triangle-free 2-matchings
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Structural properties of matroid matchings

Cited in

(26)

• An augmenting path algorithm for linear matroid parity
• Crashing a maximum-weight complementary basis
• Paroids: A canonical format for combinatorial optimization
• Structural properties of matroid matchings
• On the graphic matroid parity problem
• The linear delta-matroid parity problem
• Weighted matching with pair restrictions
• Fractional matroid matchings
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• Generalized matroid matching
• Matroid matching with Dilworth truncation
• Algebraic algorithms for linear matroid parity problems
• Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
• On the generalization of the matroid parity problem
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• scientific article; zbMATH DE number 3904606 (Why is no real title available?)
• Two algorithms for weighted matroid intersection
• scientific article; zbMATH DE number 4128828 (Why is no real title available?)
• An algorithm for weighted fractional matroid matching
• A weighted linear matroid parity algorithm
• Weighted linear matroid parity
• A weighted linear matroid parity algorithm
• Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• On matroid parity and matching polytopes

This page was built for publication: Solving the linear matroid parity problem as a sequence of matroid intersection problems

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