The computational complexity of matroid properties

DOI10.1017/S0305004100056498MaRDI QIDQ3873544zbMATH OpenFDO

Authors Gordon C. Robinson, D. 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)

Cites work

• scientific article; zbMATH DE number 3342868 (Why is no real title available?)
• Minimum partition of a matroid into independent subsets
• On recognizing graph properties from adjacency matrices
• Random matroids

Cited in

(16)

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

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

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