Finding paths of length k in O^*(2ᵏ) time
From MaRDI portal
Publication:976105
Recommendations
Cites work
- A Dynamic Programming Approach to Sequencing Problems
- Color-coding
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Designing programs that check their work
- Divide-and-Color
- Dynamic programming meets the principle of inclusion and exclusion
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Fast construction of irreducible polynomials over finite fields
- Faster Algebraic Algorithms for Path and Packing Problems
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 1004938 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Improved algorithms for path, matching, and packing problems
Cited in
(86)- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Clearing directed subgraphs by mobile agents. Variations on covering with paths
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- Long directed \((s,t)\)-path: FPT algorithm
- 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 and counting vertex-colored subtrees
- Finding temporal paths under waiting time constraints
- The maximum binary tree problem
- Univariate ideal membership parameterized by rank, degree, and number of generators
- A note on algebraic techniques for subgraph detection
- Faster deterministic parameterized algorithm for k-path
- Minimum \(k\)-path vertex cover
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- 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
- Narrow sieves for parameterized paths and packings
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Sharp separation and applications to exact and parameterized algorithms
- Constrained multilinear detection and generalized graph motifs
- Randomized parameterized algorithms for the kidney exchange problem
- A randomized algorithm for long directed cycle
- Gerrymandering on graphs: computational complexity and parameterized algorithms
- Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
- Parameterized complexity and subexponential-time computability
- What's next? Future directions in parameterized complexity
- Planar k-path in subexponential time and polynomial space
- scientific article; zbMATH DE number 3876620 (Why is no real title available?)
- Spotting trees with few leaves
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- Mixing Color Coding-Related Techniques
- Computing Pathwidth Faster Than 2 n
- On testing monomials in multivariate polynomials
- Algebraic data retrieval algorithms for multi-channel wireless data broadcast
- On the parameterized complexity of the repetition free longest common subsequence problem
- Color-coding
- Faster algorithms for finding and counting subgraphs
- Constrained multilinear detection for faster functional motif discovery
- Detecting monomials with k distinct variables
- Computing Directed Pathwidth in O(1.89 n ) Time
- Finding detours is fixed-parameter tractable
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Patching colors with tensors
- Going far from degeneracy
- Univariate ideal membership parameterized by rank, degree, and number of generators
- Graph pattern polynomials
- Approximate Counting of k-Paths: Deterministic and in Polynomial Space
- Decomposition of Map Graphs with Applications.
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Going far from degeneracy
- Engineering motif search for large motifs
- Extensor-coding
- Shortest two disjoint paths in polynomial time
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
- Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
- Exact weight subgraphs and the k-sum conjecture
- Improved deterministic algorithms for weighted matching and packing problems
- Spotting trees with few leaves
- Fast zeta transforms for lattices with few irreducibles
- scientific article; zbMATH DE number 7053391 (Why is no real title available?)
- The Maximum Binary Tree Problem.
- Parameterized complexity and kernelizability of max ones and exact ones problems
- The \(k\)-distinct language: parameterized automata constructions
- Number of cycles of small length in a graph
- Finding Temporal Paths Under Waiting Time Constraints.
- Detours in directed graphs
- Balanced substructures in bicolored graphs
- Long directed detours: reduction to 2-disjoint paths
- Approximating long cycle above Dirac's guarantee
- Parameterized algorithms for list \(K\)-cycle
- Balanced substructures in bicolored graphs
- Finding and counting patterns in sparse graphs
- Low-depth algebraic circuit lower bounds over any field
- Two-sets cut-uncut on planar graphs
- Polynomial formulations as a barrier for reduction-based hardness proofs
- Determinantal sieving
- Fixed-parameter tractability of maximum colored path and beyond
- A simple inclusion-exclusion based algorithm for (k, n)-MLC and related problems
- Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
- On approximate symmetric polynomials and tightness of homogenization results
- Fast exact algorithms using Hadamard product of polynomials
- A faster FPT algorithm for 3-path vertex cover
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Finding pathway structures in protein interaction networks
This page was built for publication: Finding paths of length \(k\) in \(O^{*}(2^k)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976105)
