TY - JOUR

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

AU - Golovnev, Alexander

AU - Kulikov, Alexander S.

AU - Mihajlin, Ivan

PY - 2014/8

Y1 - 2014/8

N2 - It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O*(2n) 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+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))n weakly connected components. One can then use a recent O*(2k) time algorithm by Gutin, Wahlström, and Yeo.

AB - It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O*(2n) 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+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))n weakly connected components. One can then use a recent O*(2k) time algorithm by Gutin, Wahlström, and Yeo.

KW - Algorithms

KW - Exact algorithm

KW - Exponential-time algorithm

KW - NP-hard problem

KW - Shortest common superstring

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=84899935055&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2014.03.004

DO - 10.1016/j.ipl.2014.03.004

M3 - Article

AN - SCOPUS:84899935055

VL - 114

SP - 421

EP - 425

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 8

ER -