Towards the graph minor theorems for directed graphs

DOI10.1007/978-3-662-47666-6_1zbMATH Open1448.05189OpenAlexW770376631MaRDI QIDQ3449461FDOQ3449461

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

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

zbMATH Keywords

directed graphsgrid minordirected disjoint paths problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Graph Minors I: A Short Proof of the Path-width Theorem
• Title not available (Why is that?)

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)