Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
From MaRDI portal
Recommendations
Cites work
- A linear vertex kernel for Maximum Internal Spanning Tree
- A new algorithm for finding trees with many leaves
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for treewidth
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Color-coding
- Contraction obstructions for treewidth
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Digraph measures: Kelly decompositions, games, and orderings
- Directed tree-width
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Fast FAST
- Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
- Finding odd cycle transversals.
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- FPT algorithms and kernels for the directed k-leaf problem
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved algorithms for feedback vertex set problems
- Improved upper bounds for vertex cover
- Kernel(s) for problems with no kernel
- Linearity of grid minors in treewidth with applications through bidimensionality
- Minimum leaf out-branching and related problems
- On finding directed trees with many leaves
- Parametrized complexity theory.
- Quickly excluding a planar graph
- Reducing to independent set structure -- the case of k-internal spanning tree
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Spanning directed trees with many leaves
- Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- The dag-width of directed graphs
- Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree
- Which problems have strongly exponential complexity?
Cited in
(10)- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Linear kernels for outbranching problems in sparse digraphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
- Adapting the directed grid theorem into an FPT algorithm
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
- Robust contraction decomposition for minor-free graphs and its applications
This page was built for publication: Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391650)
