Detours in directed graphs
From MaRDI portal
Publication:6113279
DOI10.1016/j.jcss.2023.05.001arXiv2201.03318MaRDI QIDQ6113279
William Lochet, Danil Sagunov, Fedor V. Fomin, Kirill Simonov, Petr A. Golovach, Saket Saurabh
Publication date: 10 July 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2201.03318
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Excluding pairs of graphs
- The disjoint paths problem in quadratic time
- 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
- 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
- The directed subgraph homeomorphism problem
- Hamiltonian-connected tournaments
- Long directed \((s,t)\)-path: FPT algorithm
- Graph minors. XIII: The disjoint paths problem
- Finding an induced path that is not a shortest path
- Faster deterministic parameterized algorithm for \(k\)-path
- Hamiltonicity below Dirac's condition
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Narrow sieves for parameterized paths and packings
- The linear arrangement problem parameterized above guaranteed value
- Graph Theory
- The Directed Grid Theorem
- 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
- Faster Algebraic Algorithms for Path and Packing Problems
- Divide-and-Color
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
- On Linear Time Minor Tests with Depth-First Search
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Finding k Disjoint Paths in a Directed Planar Graph
- Color-coding
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- The next‐to‐shortest path problem on directed graphs with positive edge weights
- Faster Parameterized Algorithms Using Linear Programming
- LIMITS and Applications of Group Algebras for Parameterized Problems
- Representative Families of Product Families
- Finding Detours is Fixed-Parameter Tractable
- Going Far from Degeneracy
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Digraphs
- Parameterized Traveling Salesman Problem: Beating the Average
- Multiplicative Parameterization Above a Guarantee
This page was built for publication: Detours in directed graphs
