Approximation algorithms for the shortest common superstring problem

DOI10.1016/0890-5401(89)90044-8zbMath0679.68101OpenAlexW2080721852MaRDI QIDQ1822981

Jonathan S. Turner

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1833&context=cse_research

zbMATH Keywords

NP-completeapproximation algorithmsshortest common superstring problemMcCreight's compact suffix tree construction algorithmSleator and Tarjan's lexicographic splay tree data structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Discrete mathematics in relation to computer science (68R99)

Related Items (22)

DNA sequencing and string learning ⋮ Approximating shortest superstrings with constraints ⋮ Parallel and sequential approximation of shortest superstrings ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ Improved length bounds for the shortest superstring problem ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ A Probabilistic PTAS for Shortest Common Superstring ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ Physical mapping of chromosomes: A combinatorial problem in molecular biology ⋮ A probabilistic PTAS for shortest common superstring ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Collapsing Superstring Conjecture ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ An efficient algorithm for the all pairs suffix-prefix problem ⋮ CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM ⋮ NC algorithms for finding a maximal set of paths with application to compressing strings ⋮ A note on shortest superstrings with flipping ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Approximating shortest superstrings with constraints ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Why greed works for shortest common superstring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding minimal length superstrings
• Self-adjusting binary search trees
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Linear Algorithm for Data Compression via String Matching
• Data compression via textual substitution
• Information compression by factorising common strings
• A Space-Economical Suffix Tree Construction Algorithm
• An Algorithm for Reconstructing Protein and RNA Sequences

This page was built for publication: Approximation algorithms for the shortest common superstring problem