Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-28T13:13:58.081Z Has data issue: false hasContentIssue false
  • English
  • Français

The computational complexity of matroid properties

Published online by Cambridge University Press:  24 October 2008

G. C. Robinson  and
D. J. A. Welsh
G. C. Robinson
Affiliation:
Merton College, Oxford
D. J. A. Welsh
Affiliation:
Merton College, Oxford
Get access Rights & Permissions [Opens in a new window]

Extract

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).

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 87 , Issue 1 , January 1980 , pp. 29 - 45
Copyright
Copyright © Cambridge Philosophical Society 1980

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Best, M. R., van Emde Boas, P. and Lenstra, H. W. Jr., A sharpened version of the Aanderaa-Rosenberg conjecture. Math. Centrum Amsterdam (1974).Google Scholar
(2)Bixby, R. E. and Cunningham, W. H. Matroids graphs and 3-connectivity. Graph Theory and Related Topics, ed. Bondy, J. A. and Murty, U. S. R. (New York, Academic Press) (1979), 91–103.Google Scholar
(3)Bollobás, B.Extremal Graph Theory. London Math. Soc. Monograph 11 (Academic Press, 1978).Google Scholar
(4)Bollobás, B. and Eldridge, S. E.Packings of graphs and applications to computational complexity. J. Combinatorial Theory B 24 (1978).Google Scholar
(5)Crapo, H. H. and Rota, G. C.On the foundations of combinatorial theory: Combinatorial geometries (Cambridge, Mass., M.I.T. Press, 1970).Google Scholar
(6)Cunningham, W. H. A combinatorial decomposition theory. Thesis, University of Waterloo (1973).Google Scholar
(7)Cunningham, W. H. and Edmonds, J. Decomposition of matroids and linear systems. (To appear.)Google Scholar
(8)Edmonds, J.Minimum partition of a matroid into independent sets. J. Res. Nat. Bur. Stand. 69B (1965), 67–72.CrossRefGoogle Scholar
(9)Hausmann, D. and Korte, B.Lower bounds on the worst case complexity of some oracle algorithms. University of Bonn, Report No. 7757-OR (1977).Google Scholar
(10)Hausmann, D. and Korte, B.Oracle algorithms for fixed point problems – an axiomatic approach. University of Bonn, Tech. Report No. 7766-OR (1977).CrossRefGoogle Scholar
(11)Hausmann, D. and Korte, B.Worst case analysis for a class of combinatorial optimization algorithms. University of Bonn, Tech. Report No. 7776-OR (1977).Google Scholar
(12)Knuth, D. E.Random matroids. Discrete Math. 12 (1975), 341–358.CrossRefGoogle Scholar
(13)Milner, E. C. and Welsh, D. J. A. On the computational complexity of graph theoretical properties. Proc. Fifth British Combinatorial Conference (Utilitas Math.), Winnipeg (1976), 471–487.Google Scholar
(14)Rivest, R. L. and Vuillemin, J.A generalization and proof of the Aanderaa-Rosenberg conjecture. Proc. SIGACT Conf.,Albuquerque (May 1975).CrossRefGoogle Scholar
(15)Rivest, K. L. and Vuillemin, J.On recognising graph properties from adjacency matrices. Theor. Comput. Sci. 3 (1976/1977), 371–384.CrossRefGoogle Scholar
(16)Seymour, P. D. Recognizing graphic matroids. (To appear.)Google Scholar
(17)Welsh, D. J. A.Matroid Theory. London Math. Soc. Monograph 8 (Academic Press, 1976).Google Scholar