Solving SCS for bounded length strings in fewer than 2n steps

摘要: Abstract It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O ⁎ ( 2 ) time ⋅ suppresses polynomial factors the length). In this short note, we show that for any constant r, SCS length at most r solved 1 − c where = + . For this, introduce so-called hierarchical graphs allow us to reduce on directed rural postman problem graph with k weakly connected components. One then use recent algorithm by Gutin, Wahlstrom, and Yeo.