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 resultslinear matroid parity problemgraphic matching problems

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)