Detecting Matroid Minors

P. D. Seymour; P. N. Walton

doi:10.1112/jlms/s2-23.2.193

Detecting Matroid Minors

P. D. Seymour, P. N. Walton

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	193-203
Number of pages	11
Journal	Journal of the London Mathematical Society
Volume	s2-23
Issue number	2
DOIs	https://doi.org/10.1112/jlms/s2-23.2.193
State	Published - Apr 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1112/jlms/s2-23.2.193

Cite this

@article{30964c85d82845c986060986a02ac2f0,

title = "Detecting Matroid Minors",

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.",

author = "Seymour, {P. D.} and Walton, {P. N.}",

year = "1981",

month = apr,

doi = "10.1112/jlms/s2-23.2.193",

language = "English (US)",

volume = "s2-23",

pages = "193--203",

journal = "Journal of the London Mathematical Society",

issn = "0024-6107",

publisher = "Oxford University Press",

number = "2",

}

TY - JOUR

T1 - Detecting Matroid Minors

AU - Seymour, P. D.

AU - Walton, P. N.

PY - 1981/4

Y1 - 1981/4

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

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

UR - http://www.scopus.com/inward/record.url?scp=52649156241&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52649156241&partnerID=8YFLogxK

U2 - 10.1112/jlms/s2-23.2.193

DO - 10.1112/jlms/s2-23.2.193

M3 - Article

AN - SCOPUS:52649156241

SN - 0024-6107

VL - s2-23

SP - 193

EP - 203

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

IS - 2

ER -

Detecting Matroid Minors

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this