Adapting the Directed Grid Theorem into an FPT Algorithm
From MaRDI portal
Publication:5099098
DOI10.1137/21M1452664zbMath1496.05059arXiv2007.07738OpenAlexW3043413734WikidataQ113779006 ScholiaQ113779006MaRDI QIDQ5099098
Ana Karolinna Maia, Ignasi Sau, Raul Lopes, Victor A. Campos
Publication date: 31 August 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.07738
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An algorithmic metatheorem for directed treewidth
- Fundamentals of parameterized complexity
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Digraph decompositions and monotonicity in digraph searching
- Graph minors. XXI. graphs with unique linkages
- Graph minors. V. Excluding a planar graph
- The directed subgraph homeomorphism problem
- S-functions for graphs
- Graph searching and a min-max theorem for tree-width
- On directed feedback vertex set parameterized by treewidth
- Exponential polynomials
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- Digraph width measures in parameterized algorithmics
- Parametrized complexity theory.
- 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
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Polynomial Bounds for the Grid-Minor Theorem
- Quantitative Graph Theory
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Treewidth: Characterizations, Applications, and Computations
- Complexity of Finding Embeddings in a k-Tree
- Directed multicut is W[1-hard, even for four terminal pairs]
- Multicut Is FPT
- Classes of Directed Graphs
- Finding Detours is Fixed-Parameter Tractable
- A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
- Half-integral linkages in highly connected directed graphs
- The Directed Flat Wall Theorem
- Towards Tight(er) Bounds for the Excluded Grid Theorem
- Polynomial Planar Directed Grid Theorem
- An Excluded Grid Theorem for Digraphs with Forbidden Minors
- 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
- Encyclopedia of Algorithms
This page was built for publication: Adapting the Directed Grid Theorem into an FPT Algorithm
