Premium
Detecting Matroid Minors
Author(s) -
Seymour P. D.,
Walton P. N.
Publication year - 1981
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-23.2.193
Subject(s) - matroid , citation , combinatorics , computer science , mathematics , library science
When % is a collection of matroids, the question whether M has a minor in % can be easy or hard, depending on the choice of < 6. 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 % as easy or hard.