DOI

The best known approximation ratio for the shortest superstring problem is 211/23 (Mucha, 2012). In this note, we improve this bound for the case when the length of all input strings is equal to r, for r ≤ 7. E.g., for strings of length 3 we get a 11/3-approximation. An advantage of the algorithm is that it is extremely simple both to implement and to analyze. Another advantage is that it is based on de Bruijn graphs. Such graphs are widely used in genome assembly (one of the most important practical applications of the shortest common superstring problem). At the same time these graphs have only a few applications in theoretical investigations of the shortest superstring problem.

Язык оригиналаанглийский
Название основной публикацииCombinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
Страницы120-129
Число страниц10
DOI
СостояниеОпубликовано - 24 сен 2013
Событие24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 - Bad Herrenalb, Германия
Продолжительность: 17 июн 201319 июн 2013

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7922 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
Страна/TерриторияГермания
ГородBad Herrenalb
Период17/06/1319/06/13

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49826021