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)

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

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)