Adapting the directed grid theorem into an \textsf{FPT} algorithm

DOI10.1016/j.entcs.2019.08.021OpenAlexW2977692557WikidataQ113317411 ScholiaQ113317411MaRDI QIDQ2132350

Raul Lopes, Ignasi Sau, Ana Karolinna Maia, Victor A. Campos

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.021

zbMATH Keywords

directed graphsdirected tree-width\textsf{FPT} algorithmsgrid theorem

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Related Items (3)

Directed width parameters on semicomplete digraphs ⋮ Digraphs of directed treewidth one ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Graph minors. V. Excluding a planar graph
• S-functions for graphs
• Graph searching and a min-max theorem for tree-width
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• Nonserial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tour Merging via Branch-Decomposition
• The Directed Grid Theorem
• Polynomial Bounds for the Grid-Minor Theorem
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Treewidth: Characterizations, Applications, and Computations
• Directed multicut is W[1-hard, even for four terminal pairs]
• Multicut Is FPT
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Parameterized Algorithms
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

This page was built for publication: Adapting the directed grid theorem into an \textsf{FPT} algorithm