A Fast, Simpler Algorithm for the Matroid Parity Problem

DOI10.1007/978-3-540-68891-4_17zbMath1143.90382OpenAlexW1562618686WikidataQ59592363 ScholiaQ59592363MaRDI QIDQ3503851

James B. Orlin

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68891-4_17

zbMATH Keywords

matroid paritymatroid matchingmatroid intersectionnonbipartite matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (14)

Boundary classes for graph problems involving non-local properties ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Weighted matching with pair restrictions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Unnamed Item ⋮ On matroid parity and matching polytopes ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

This page was built for publication: A Fast, Simpler Algorithm for the Matroid Parity Problem