Detecting Matroid Minors

P. D. Seymour, P. N. Walton

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

When formula presented is a collection of matroids, the question whether M has a minor in formula presented can be easy or hard, depending on the choice of More precisely, the number of demands made on an “independence oracle” to decide the question sometimes can be bounded above by a polynomial in E(M), and sometimes it cannot. We study this, and in particular classify each singleton formula presented as easy or hard.

Original languageEnglish (US)
Pages (from-to)193-203
Number of pages11
JournalJournal of the London Mathematical Society
Volumes2-23
Issue number2
DOIs
StatePublished - Apr 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Detecting Matroid Minors'. Together they form a unique fingerprint.

  • Cite this