Long directed \((s,t)\)-path: FPT algorithm

DOI10.1016/j.ipl.2018.04.018zbMath1478.68233OpenAlexW2806209209MaRDI QIDQ1799598

Meirav Zehavi, Fahad Panolan, Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov

Publication date: 19 October 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.018

zbMATH Keywords

long directed cycleparameterized algorithmlong directed \((s,t)\)-path

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Optimizing concurrency under Scheduling by Edge Reversal ⋮ Detours in directed graphs ⋮ Going Far from Degeneracy ⋮ Unnamed Item ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Two edge-disjoint paths with length constraints

Cites Work

• A randomized algorithm for long directed cycle
• Representative families: a unified tradeoff-based approach
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Narrow sieves for parameterized paths and packings
• Representative Sets of Product Families
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Mixing Color Coding-Related Techniques
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Finding a long directed cycle
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

This page was built for publication: Long directed \((s,t)\)-path: FPT algorithm