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

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

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