Approximation algorithms for the shortest common superstring problem

DOI10.1016/0890-5401(89)90044-8MaRDI QIDQ1822981zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsNP-completeshortest common superstring problemMcCreight's compact suffix tree construction algorithmSleator and Tarjan's lexicographic splay tree data structure

Mathematics Subject Classification ID

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

Recommendations

• A greedy approximation algorithm for constructing shortest common superstrings
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• A linear-time algorithm for finding approximate shortest common superstrings
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Reoptimization of the shortest common superstring problem
• Reoptimization of the Shortest Common Superstring Problem
• scientific article; zbMATH DE number 827942
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Publication:4725747

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3913713 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• A Space-Economical Suffix Tree Construction Algorithm
• An Algorithm for Reconstructing Protein and RNA Sequences
• Data compression via textual substitution
• Information compression by factorising common strings
• Linear Algorithm for Data Compression via String Matching
• On finding minimal length superstrings
• Self-adjusting binary search trees

Cited in

(44)

• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Greedy shortest common superstring approximation in compact space
• An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
• An efficient algorithm for the all pairs suffix-prefix problem
• Improved length bounds for the shortest superstring problem
• Combinatorial algorithms for DNA sequence assembly
• A probabilistic PTAS for shortest common superstring
• Collapsing Superstring Conjecture
• scientific article; zbMATH DE number 3999290 (Why is no real title available?)
• A Probabilistic PTAS for Shortest Common Superstring
• Lyndon words and short superstrings
• NC algorithms for finding a maximal set of paths with application to compressing strings
• Approximating shortest superstring problem using de Bruijn graphs
• Reoptimization of the shortest common superstring problem
• On the greedy algorithm for the shortest common superstring problem with reversals
• The constrained shortest common supersequence problem
• The shortest superstring problem
• A note on shortest superstrings with flipping
• scientific article; zbMATH DE number 2079866 (Why is no real title available?)
• A linear-time algorithm for finding approximate shortest common superstrings
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• More on the complexity of common superstring and supersequence problems
• scientific article; zbMATH DE number 1973869 (Why is no real title available?)
• Why Greed Works for Shortest Common Superstring Problem
• Restricted common superstring and restricted common supersequence
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• Solving 3-superstring in \(3^{n/3}\) time
• Why greed works for shortest common superstring problem
• Reoptimization of the Shortest Common Superstring Problem
• Approximating shortest superstrings with constraints
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• scientific article; zbMATH DE number 5074400 (Why is no real title available?)
• Approximating shortest superstrings with constraints
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• DNA sequencing and string learning
• Parallel and sequential approximation of shortest superstrings
• Two approaches to the common superstring problem
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• scientific article; zbMATH DE number 827942 (Why is no real title available?)
• A \(2_3^2\) superstring approximation algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822981)