New algorithms for linear k-matroid intersection and matroid k-parity problems

DOI10.1007/BF01585571MaRDI QIDQ1906282zbMATH OpenOpenAlexFDO

Authors Alexander Barvinok

Publication date 2 September 1996

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01585571

zbMATH Keywords

\(k\)-dimensional assignment problem\(k\)-dimensional matching problem\(k\)-matroid intersection problemhyperdeterminantmatroid \(k\)-parity problem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial optimization (90C27)

Recommendations

• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for matching and matroid problems

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the computation of pfaffians
• Random pseudo-polynomial algorithms for exact matroid problems

Cited in

(21)

• A parameterized view on matroid optimization problems
• An augmenting path algorithm for linear matroid parity
• Quantum hyperdeterminants and hyper-Pfaffians
• Binary linear codes, dimers and hypermatrices
• Pfaffian and Hafnian identities in shuffle algebras
• The Grassmann-Berezin calculus and theorems of the matrix-tree type
• Tensor slice rank and Cayley's first hyperdeterminant
• Ensemble averages when \(\beta \) is a square integer
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Algebraic algorithms for matching and matroid problems
• scientific article; zbMATH DE number 3904590 (Why is no real title available?)
• A sign-reversing involution for an extension of Torelli's Pfaffian identity
• Bounds on the number of connected components for tropical prevarieties
• Generating functions and counting formulas for spanning trees and forests in hypergraphs
• Hyperdeterminantal total positivity
• Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
• Polynomial kernels with reachability for weighted d-matroid intersection
• Hyperdeterminantal point processes
• An efficient tree decomposition method for permanents and mixed discriminants
• Hyperdeterminantal expressions for Jack functions of rectangular shapes
• Hankel hyperdeterminants, rectangular Jack polynomials and even powers of the Vandermonde

This page was built for publication: New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems

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