A Fast, Simpler Algorithm for the Matroid Parity Problem

DOI10.1007/978-3-540-68891-4_17MaRDI QIDQ3503851zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 intersectionmatroid matchingmatroid paritynonbipartite matching

Mathematics Subject Classification ID

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

Recommendations

• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for linear matroid parity problems
• On the generalization of the matroid parity problem
• scientific article; zbMATH DE number 3904590
• Parallel algorithms for matroid intersection and matroid parity
• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• On the graphic matroid parity problem
• An augmenting path algorithm for linear matroid parity
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems

Cited in

(21)

• An augmenting path algorithm for linear matroid parity
• Weighted matching with pair restrictions
• 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
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Boundary classes for graph problems involving non-local properties
• Packing A-paths in group-labelled graphs via linear matroid parity
• Algebraic algorithms for linear matroid parity problems
• A deterministic PTAS for the commutative rank of matrix spaces
• A tight extremal bound on the Lovász cactus number in planar graphs
• Weighted linear matroid parity
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• A polynomial kernel for distance-hereditary vertex deletion
• Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
• An improved algorithm for finding maximum outerplanar subgraphs
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• Local optimization algorithms for maximum planar subgraph
• On matroid parity and matching polytopes

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

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