Finding paths of length k in O*(2^k) time

2008/07/31 by Ryan Williams · 1 citation
Computer Science · #cs.DS #cs.DM

paper · pdf

published as Information Processing Letters, 109(6):315--318, February 2009 · 7 pages. Revised version to appear in Information Processing Letters

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.

Cited by

• Kronecker scaling of tensors with applications to arithmetic circuits and algorithms