| Popis: |
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O ⁎ ( 2 n ) time ( 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 ) where c ( r ) = ( 1 + 2 r 2 ) − 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 ) ) n weakly connected components. One can then use a recent O ⁎ ( 2 k ) time algorithm by Gutin, Wahlstrom, and Yeo. |
Full Text from ScienceDirect