В докладе будет рассказано, как эффективно решать задачу о наименьшей общей надстроке для ее частных, но все еще NP-полных случаев. Будут представлены 2 алгоритма:
1)находящий точное решение для случая, когда все строки длины не больше 3, за $3^{n/3}$, вместо лучшего известного, дающего $2^n$ для общего случая.
2)дающий лучшее приближение чем имеющиеся на данный момент приближающие алгоритмы для общего случая если все строки короче 7 символов.