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 languageEnglish
Title of host publicationCombinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
Pages120-129
Number of pages10
DOIs
StatePublished - 24 Sep 2013
Event24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 - Bad Herrenalb, Germany
Duration: 17 Jun 201319 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7922 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
Country/TerritoryGermany
CityBad Herrenalb
Period17/06/1319/06/13

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49826021