Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings |
Pages | 120-129 |
Number of pages | 10 |
DOIs | |
State | Published - 24 Sep 2013 |
Event | 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 - Bad Herrenalb, Germany Duration: 17 Jun 2013 → 19 Jun 2013 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 7922 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 |
---|---|
Country/Territory | Germany |
City | Bad Herrenalb |
Period | 17/06/13 → 19/06/13 |
ID: 49826021