Mathematical Proceedings of the Cambridge Philosophical Society · 1980 · 50 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityGraph AlgorithmsGraph TheoryMatroid TheoryComputational Complexity Of Graph AlgorithmsOracle Machines
Knuth (12) seems to have been the first to carry out non-trivial matroid operations on a computer. However, as he remarks, there are considerable computational difficulties. In this paper we examine in detail the computational complexity of some fundamental matroid properties. The model of computation is the Hausmann–Korte oracle machine introduced in (10), (11) to deal with properties of independence spaces and fixed point problems. It was these papers (10), (11) and (12) which motivated the present work. Basically, the problems we will be discussing are matroid analogues of low-level complexity problems for graphs. For an excellent survey of this we refer to the recent monograph of Bollobés ((3), chapter 8). We shall use the approach of (3), and Bollobaé;s and Eldridge(4) rather than the more general treatment of Hausmann and Korte (11).
8
A Combinatorial Decomposition Theory
William H. Cunningham, Jack Edmonds · Canadian Journal of Mathematics · 1980 · 331 citations · Full text
Paul Seymour · COMBINATORICA · 1981 · 98 citations