Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 июн 2013 → 19 июн 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/13 → 19/06/13 |
ID: 49826021