Adapting the directed grid theorem into an \textsf{FPT} algorithm
From MaRDI portal
Publication:2132350
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
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
