Complexity of Matroid Property Algorithms
From MaRDI portal
Publication:3936197
DOI10.1137/0211014zbMath0478.68044OpenAlexW1978185401MaRDI QIDQ3936197
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211014
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Algorithms in computer science (68W99)
Related Items
On complexity of maximizatin of submodular functions* ⋮ An augmenting path algorithm for linear matroid parity ⋮ Optimization problems with color-induced budget constraints ⋮ New applications of partial orders ⋮ Packing non-zero \(A\)-paths via matroid matching ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Singular spaces of matrices and their application in combinatorics ⋮ An application of submodular flows ⋮ Independence and port oracles for matroids, with an application to computational learning theory ⋮ Optimal general factor problem and jump system intersection ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ On the graphic matroid parity problem ⋮ The linear delta-matroid parity problem ⋮ On the complexity of packing rainbow spanning trees ⋮ Matroid Intersection under Restricted Oracles ⋮ Recent Developments in Discrete Convex Analysis ⋮ Probabilistic single processor scheduling ⋮ An algorithm for weighted fractional matroid matching ⋮ A simple PTAS for weighted matroid matching on strongly base orderable matroids ⋮ Recognizing graphic matroids ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Structural properties of matroid matchings ⋮ Matroid matching with Dilworth truncation ⋮ Greedoids and Linear Objective Functions ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Lattice path matroids: structural properties ⋮ The parity problem of polymatroids without double circuits ⋮ On some combinatorial properties of algebraic matroids ⋮ Combinatorial auctions with decreasing marginal utilities ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Complexity of packing common bases in matroids ⋮ Fractional matroid matchings ⋮ Solving the linear matroid parity problem as a sequence of matroid intersection problems ⋮ Generalized matroid matching ⋮ Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization ⋮ Unnamed Item ⋮ A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids ⋮ On matroid parity and matching polytopes ⋮ The computational complexity of knot and matroid polynomials
