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

DOI10.1007/BF01580854zbMath0813.90097OpenAlexW2154896222WikidataQ59592682 ScholiaQ59592682MaRDI QIDQ1813836

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

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

Related Items

Finding Maximum Edge-Disjoint Paths Between Multiple Terminals, Two algorithms for weighted matroid intersection, The linear delta-matroid parity problem, An algorithm for weighted fractional matroid matching, A Weighted Linear Matroid Parity Algorithm, Weighted matching with pair restrictions, Crashing a maximum-weight complementary basis, Structural properties of matroid matchings, Matroid matching with Dilworth truncation, Algebraic Algorithms for Linear Matroid Parity Problems, Fractional matroid matchings, Solving the linear matroid parity problem as a sequence of matroid intersection problems, Unnamed Item, On matroid parity and matching polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• An extension of matching theory
• An augmenting path algorithm for linear matroid parity
• Matroid matching and some applications
• Structural properties of matroid matchings
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Multi-Terminal Network Flows
• Perfect triangle-free 2-matchings
• Optimum matching forests I: Special weights
• Complexity of Matroid Property Algorithms
• Matroid intersection algorithms
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Optimal Sequencing of Two Equivalent Processors
• Matroids and the greedy algorithm