| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6874104 | Information Processing Letters | 2018 | 9 Pages |
Abstract
Given a digraph G, two vertices s,tâV(G) and a non-negative integer k, the Long Directed(s,t)-Path problem asks whether G has a path of length at least k from s to t. We present a simple algorithm that solves Long Directed(s,t)-Path in time Oâ(4.884k). This results also in an improvement upon the previous fastest algorithm for Long Directed Cycle.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi,