The computational complexity of matroid properties

DOI10.1017/S0305004100056498zbMATH Open0434.68030MaRDI QIDQ3873544FDOQ3873544

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

• Minimum partition of a matroid into independent subsets
• Title not available (Why is that?)
• On recognizing graph properties from adjacency matrices
• Random matroids

Cited In (16)

• 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
• Matroid Intersection under Restricted Oracles
• Some problems on approximate counting in graphs and matroids
• Recognizing Polymatroids Associated with Hypergraphs
• Tutte polynomials computable in polynomial time
• 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
• The computational complexity of antimatroid properties
• Color-avoiding connected spanning subgraphs with minimum number of edges

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)