Finding paths of length k in O*(2^k) time
arXiv:0807.3026
Abstract
We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(2^k poly(n,k)) time.
7 pages. Revised version to appear in Information Processing Letters
Cited by in corpus (8)
- Minimum k-path vertex cover
- Finding and counting vertex-colored subtrees
- Constrained multilinear detection for faster functional motif discovery
- Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function
- The fast intersection transform with applications to counting paths
- Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials
- Stationary Algorithmic Balancing For Dynamic Email Re-Ranking Problem
- The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)