کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427450 | 686508 | 2014 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Solving SCS for bounded length strings in fewer than 2n2n steps Solving SCS for bounded length strings in fewer than 2n2n steps](/preview/png/427450.png)
• We study the shortest common superstring problem on string of length r (r-SCS).
• We introduce hierarchical graphs to reduce the r-SCS problem to the directed rural postman problem (DRPP).
• We bound the number of weakly connected components in hierarchical graphs and call recent algorithm by Gutin et al.
• The main result is a randomized 2n(1−Ω(r−2))2n(1−Ω(r−2))-time algorithm for r-SCS.
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O⁎(2n)O⁎(2n) time (O⁎(⋅)O⁎(⋅) suppresses polynomial factors of the input length). In this short note, we show that for any constant r, SCS for strings of length at most r can be solved in time O⁎(2(1−c(r))n)O⁎(2(1−c(r))n) where c(r)=(1+2r2)−1c(r)=(1+2r2)−1. For this, we introduce so-called hierarchical graphs that allow us to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k=(1−c(r))nk=(1−c(r))n weakly connected components. One can then use a recent O⁎(2k)O⁎(2k) time algorithm by Gutin, Wahlström, and Yeo.
Journal: Information Processing Letters - Volume 114, Issue 8, August 2014, Pages 421–425