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)

Full work available at URL https://doi.org/10.1017/S0305004100056498

zbMATH Keywords

oracle Turing machines

Mathematics Subject Classification ID

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

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

(19)

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