Finding Detours is Fixed-Parameter Tractable
From MaRDI portal
Publication:4972756
DOI10.1137/17M1148566zbMath1428.05161arXiv1607.07737OpenAlexW4210959657WikidataQ126625047 ScholiaQ126625047MaRDI QIDQ4972756
Holger Dell, Radu Curticapean, Fedor V. Fomin, Ivona Bezáková
Publication date: 27 November 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.07737
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)
Related Items
Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Detours in directed graphs ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Going Far from Degeneracy
Uses Software
Cites Work
- Unnamed Item
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Vertex cover problem parameterized above and below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- Linear kernels and linear-time algorithms for finding large cuts
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Parameterizing above or below guaranteed values
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- On limited nondeterminism and the complexity of the V-C dimension
- Tree-width and planar minors
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Narrow sieves for parameterized paths and packings
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Large Independent Sets in Subquartic Planar Graphs
- Graph Theory
- The Directed Grid Theorem
- Low Polynomial Exclusion of Planar Graph Patterns
- Polynomial Kernels for {\lambda}-extendible Properties Parameterized Above the Poljak-Turz\'ik Bound
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Polynomial Bounds for the Grid-Minor Theorem
- Mixing Color Coding-Related Techniques
- Faster Algebraic Algorithms for Path and Packing Problems
- Divide-and-Color
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- On Linear Time Minor Tests with Depth-First Search
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Color-coding
- Towards Tight(er) Bounds for the Excluded Grid Theorem
- Large Independent Sets in Triangle-Free Planar Graphs
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: Finding Detours is Fixed-Parameter Tractable
