| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427861 | Information Processing Letters | 2009 | 4 Pages |
Abstract
We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(k2⋅poly(n)) time. Our method extends a recent O(23k/2⋅poly(n))⩽O(k2.83⋅poly(n)) algorithm of Koutis.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
