Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav (2018) Long directed (s,t)-path: FPT algorithm Information Processing Letters, 140 . pp. 8-12. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.ipl.2018.04.018
Related URL: http://dx.doi.org/10.1016/j.ipl.2018.04.018
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123378 |
| Deposited On: | 15 Sep 2021 11:22 |
| Last Modified: | 15 Sep 2021 11:22 |
Repository Staff Only: item control page
