SIAM Journal on Computing · 1982 · 131 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityComputational ComplexityMatroid TheoryStructural ComplexityRepresentable MatroidsTest Oracle Problem
A general theorem is proved which can be used to show that for a large number of matroid properties there is no good algorithm of a certain type for determining whether these properties hold for general matroids. Specifically, there exists no algorithm in which the matroid is represented by an independence test oracle (or an oracle polynomially related to an independence test oracle) and which solves the problem in question after a number of calls on the oracle which is bounded by a polynomial in the number of elements of the ground set of the matroid.
7
Robert G. Bland, Michel Las Vergnas · Journal of Combinatorial Theory Series B · 1978 · 260 citations
Matroid matching and some applications
László Lovász · Journal of Combinatorial Theory Series B · 1980 · 178 citations
Paul Seymour · COMBINATORICA · 1981 · 98 citations