Tournament immersion and cutwidth
Author(s): Chudnovsky, Maria; Fradkin, Alexandra; Seymour, Paul D.
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1795m
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chudnovsky, Maria | - |
dc.contributor.author | Fradkin, Alexandra | - |
dc.contributor.author | Seymour, Paul D. | - |
dc.date.accessioned | 2018-07-20T15:09:10Z | - |
dc.date.available | 2018-07-20T15:09:10Z | - |
dc.date.issued | 2012-01 | en_US |
dc.identifier.citation | Chudnovsky, Maria, Fradkin, Alexandra, Seymour, Paul. (2012). Tournament immersion and cutwidth. JOURNAL OF COMBINATORIAL THEORY SERIES B, 102 (93 - 101. doi:10.1016/j.jctb.2011.05.001 | en_US |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr1795m | - |
dc.description.abstract | A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered (v(1), ... , v(n)) in such a way that for each j, there are at most k edges uv such that u is an element of v(1), ... , v(j-1) and v is an element of v(j), ... , v(n). We prove that for every set S of tournaments, the following are equivalent: there is a digraph H such that H cannot be strongly immersed in any member of S. there exists k such that every member of S has cutwidth at most k, there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles. This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament. (C) 2011 Elsevier Inc. All rights reserved. | en_US |
dc.format.extent | 93 - 101 | en_US |
dc.language.iso | en_US | en_US |
dc.relation.ispartof | JOURNAL OF COMBINATORIAL THEORY SERIES B | en_US |
dc.rights | Final published version. Article is made available in OAR by the publisher's permission or policy. | en_US |
dc.title | Tournament immersion and cutwidth | en_US |
dc.type | Journal Article | en_US |
dc.identifier.doi | doi:10.1016/j.jctb.2011.05.001 | - |
dc.date.eissued | 2011-06-01 | en_US |
pu.type.symplectic | http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article | en_US |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1-s2.0-S009589561100061X-main.pdf | 168.21 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.