Towards the graph minor theorems for directed graphs

DOI10.1007/978-3-662-47666-6_1MaRDI QIDQ3449461zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Stephan Kreutzer

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47666-6_1

zbMATH Keywords

directed disjoint paths problemdirected graphsgrid minor

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph minors (05C83)

Recommendations

• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• The directed grid theorem
• An excluded grid theorem for digraphs with forbidden minors
• Polynomial planar directed grid theorem
• Adapting the directed grid theorem into an FPT algorithm

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• An excluded grid theorem for digraphs with forbidden minors
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Bidimensional Parameters and Local Treewidth
• Bidimensionality: new connections between FPT algorithms and PTASs
• Directed tree-width
• Finding k Disjoint Paths in a Directed Planar Graph
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Highly connected sets and the excluded grid theorem
• scientific article; zbMATH DE number 5764892 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• Introducing directed tree width
• Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linearity of grid minors in treewidth with applications through bidimensionality
• Packing directed circuits
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Polynomial bounds for the grid-minor theorem
• Quickly excluding a planar graph
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The directed grid theorem
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• Tree-width and planar minors

Cited in

(9)

• Adapting the directed grid theorem into an \textsf{FPT} algorithm
• The directed grid theorem
• Graph Minors I: A Short Proof of the Path-width Theorem
• scientific article; zbMATH DE number 7378361 (Why is no real title available?)
• Constant congestion brambles in directed graphs
• Adapting the directed grid theorem into an FPT algorithm
• Directed path-decompositions
• Polynomial planar directed grid theorem
• An excluded grid theorem for digraphs with forbidden minors

This page was built for publication: Towards the graph minor theorems for directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449461)