کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427038 | 686427 | 2016 | 4 صفحه PDF | دانلود رایگان |
• We present a parameterized algorithm, LDC-Alg, for Long Directed Cycle.
• Currently, LDC-Alg is the fastest algorithm for Long Directed Cycle.
• LDC-Alg can use any algorithm for k-Path as a black box.
Given a directed graph G and a parameter k, the Long Directed Cycle (LDC) problem asks whether G contains a simple cycle on at least k vertices, while the k-Path problem asks whether G contains a simple path on exactly k vertices. Given a deterministic (randomized) algorithm for k-Path as a black box, which runs in time t(G,k)t(G,k), we prove that LDC can be solved in deterministic time O⁎(max{t(G,2k),4k+o(k)})O⁎(max{t(G,2k),4k+o(k)}) or in randomized time O⁎(max{t(G,2k),4k})O⁎(max{t(G,2k),4k}). In particular, we get that LDC can be solved in randomized time O⁎(4k)O⁎(4k).
Journal: Information Processing Letters - Volume 116, Issue 6, June 2016, Pages 419–422