Finding paths of length \(k\) in \(O^{*}(2^k)\) time
From MaRDI portal
Publication:976105
DOI10.1016/J.IPL.2008.11.004zbMath1191.68857OpenAlexW1852383912WikidataQ56639269 ScholiaQ56639269MaRDI QIDQ976105
Publication date: 16 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.11.004
Related Items (69)
A randomized algorithm for long directed cycle ⋮ A note on algebraic techniques for subgraph detection ⋮ Spotting Trees with Few Leaves ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Spotting Trees with Few Leaves ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Mixing Color Coding-Related Techniques ⋮ Randomized parameterized algorithms for the kidney exchange problem ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Narrow sieves for parameterized paths and packings ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Parameterized complexity of superstring problems ⋮ Gerrymandering on graphs: computational complexity and parameterized algorithms ⋮ On testing monomials in multivariate polynomials ⋮ Algebraic data retrieval algorithms for multi-channel wireless data broadcast ⋮ Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms ⋮ Number of cycles of small length in a graph ⋮ Detours in directed graphs ⋮ On the parameterized complexity of the repetition free longest common subsequence problem ⋮ Balanced substructures in bicolored graphs ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Finding and counting vertex-colored subtrees ⋮ Faster algorithms for finding and counting subgraphs ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Constrained multilinear detection for faster functional motif discovery ⋮ Going Far from Degeneracy ⋮ Detecting monomials with \(k\) distinct variables ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ The Maximum Binary Tree Problem. ⋮ Finding temporal paths under waiting time constraints ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Minimum \(k\)-path vertex cover ⋮ Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ The maximum binary tree problem ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Decomposition of Map Graphs with Applications. ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Unnamed Item ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ Nouvelle demonstration d'une congruence modulo 16 entre les nombres de classes d'ideaux de \(Q(\sqrt{-2p})\) et \(Q(\sqrt{2p})\) pour p premier = 1 (mod 4) ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy ⋮ A fast parallel algorithm for minimum-cost small integral flows ⋮ Constrained multilinear detection and generalized graph motifs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic programming meets the principle of inclusion and exclusion
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Faster Algebraic Algorithms for Path and Packing Problems
- Divide-and-Color
- Designing programs that check their work
- Color-coding
- Fast construction of irreducible polynomials over finite fields
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Finding paths of length \(k\) in \(O^{*}(2^k)\) time
