Faster deterministic parameterized algorithm for \(k\)-path
From MaRDI portal
Publication:2272387
DOI10.1016/j.tcs.2019.04.024zbMath1430.68247arXiv1808.04185OpenAlexW2953017342WikidataQ127832309 ScholiaQ127832309MaRDI QIDQ2272387
Publication date: 10 September 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.04185
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
A note on algebraic techniques for subgraph detection ⋮ QUBO formulations of the longest path problem ⋮ Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms ⋮ Detours in directed graphs ⋮ Going Far from Degeneracy ⋮ Unnamed Item ⋮ Two edge-disjoint paths with length constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Parameterized approximation algorithms for packing problems
- Representative families: a unified tradeoff-based approach
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Long directed \((s,t)\)-path: FPT algorithm
- Narrow sieves for parameterized paths and packings
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- 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
- Color-coding
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
This page was built for publication: Faster deterministic parameterized algorithm for \(k\)-path