Graph Minors. XXII. Irrelevant vertices in linkage problems

Neil Robertson; Paul Seymour

doi:10.1016/j.jctb.2007.12.007

Graph Minors. XXII. Irrelevant vertices in linkage problems

Neil Robertson, Paul Seymour

Mathematics

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

32 Scopus citations

Abstract

In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently "insulated" from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.

Original language	English (US)
Pages (from-to)	530-563
Number of pages	34
Journal	Journal of Combinatorial Theory. Series B
Volume	102
Issue number	2
DOIs	https://doi.org/10.1016/j.jctb.2007.12.007
State	Published - Mar 2012

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Disjoint paths algorithm
Graph minors
Irrelevant vertex
Linkage problem

Access to Document

10.1016/j.jctb.2007.12.007

Cite this

@article{49fbec3e7e854699b97137273e69f33e,

title = "Graph Minors. XXII. Irrelevant vertices in linkage problems",

abstract = "In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently {"}insulated{"} from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.",

keywords = "Disjoint paths algorithm, Graph minors, Irrelevant vertex, Linkage problem",

author = "Neil Robertson and Paul Seymour",

note = "Funding Information: E-mail address: pds@math.princeton.edu (P. Seymour). 1 Partially supported by NSF grant DMS 8903132. 2 This work was carried out while this author was employed at Telcordia Technologies in Morristown, NJ.",

year = "2012",

month = mar,

doi = "10.1016/j.jctb.2007.12.007",

language = "English (US)",

volume = "102",

pages = "530--563",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Graph Minors. XXII. Irrelevant vertices in linkage problems

AU - Robertson, Neil

AU - Seymour, Paul

N1 - Funding Information: E-mail address: pds@math.princeton.edu (P. Seymour). 1 Partially supported by NSF grant DMS 8903132. 2 This work was carried out while this author was employed at Telcordia Technologies in Morristown, NJ.

PY - 2012/3

Y1 - 2012/3

N2 - In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently "insulated" from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.

AB - In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently "insulated" from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.

KW - Disjoint paths algorithm

KW - Graph minors

KW - Irrelevant vertex

KW - Linkage problem

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

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

U2 - 10.1016/j.jctb.2007.12.007

DO - 10.1016/j.jctb.2007.12.007

M3 - Article

AN - SCOPUS:84856732037

SN - 0095-8956

VL - 102

SP - 530

EP - 563

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Graph Minors. XXII. Irrelevant vertices in linkage problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this