Edge-disjoint paths in digraphs with bounded independence number

DOI10.1016/j.jctb.2014.07.002zbMath1302.05067MaRDI QIDQ473097

P. D. Seymour, Alexandra Ovetsky Fradkin

Publication date: 21 November 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2014.07.002

zbMATH Keywords

independence number; digraphs; tournaments; polynomial-time algorithm; disjoint paths; linking problem

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C20: Directed graphs (digraphs), tournaments