The computational complexity of matroid properties

DOI10.1017/S0305004100056498zbMath0434.68030MaRDI QIDQ3873544

Gordon C. Robinson, Dominic J. A. Welsh

Publication date: 1980

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

zbMATH Keywords

oracle Turing machines

Mathematics Subject Classification ID

Related Items (16)

First order convergence of matroids ⋮ Recognizing Polymatroids Associated with Hypergraphs ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Modularity and greed in double auctions ⋮ Color-avoiding connected spanning subgraphs with minimum number of edges ⋮ On Fair Division under Heterogeneous Matroid Constraints ⋮ Matroid Intersection under Restricted Oracles ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Recognizing graphic matroids ⋮ Tutte polynomials computable in polynomial time ⋮ The computational complexity of antimatroid properties ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Complexity of packing common bases in matroids ⋮ On the efficiency of representability tests for matroids ⋮ The computational complexity of knot and matroid polynomials ⋮ On the problem of approximating the number of bases of a matroid

Cites Work

• Random matroids
• On recognizing graph properties from adjacency matrices
• Minimum partition of a matroid into independent subsets
• Unnamed Item

This page was built for publication: The computational complexity of matroid properties