Solving the linear matroid parity problem as a sequence of matroid intersection problems
The authors present an \(O(r^ 4 n)\) algorithm for the following linear matroid parity problem. Let \(A\) be an \(r\times 2n\) matrix over a field \(F\) with columns partitioned into pairs \(A(1),\dots, A(n)\). Find a collection \(A(i_ 1),\dots, A(i_ k)\) of maximal cardinality \(k\) consisting of linearly independent columns. This problem is imbedded into a wider class of optimization problems where \(\text{card }A(i_ j)\) is not necessarily equal to 2 and then is replaced by a sequence of so- called ``easy parity problems each of which can be solved as a matroid intersection problem. By certain duality results it follows that one can indeed obtain an optimal solution of the initial problem. Some connections with graphic matching problems are considered.
- 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
- 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)
