Approximation algorithms for the shortest common superstring problem

DOI10.1016/0890-5401(89)90044-8zbMATH Open0679.68101OpenAlexW2080721852MaRDI QIDQ1822981FDOQ1822981

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

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

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)

Cites Work

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

Cited In (44)

• A probabilistic PTAS for shortest common superstring
• Reoptimization of the shortest common superstring problem
• The constrained shortest common supersequence problem
• Title not available (Why is that?)
• Approximating shortest superstrings with constraints
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Collapsing Superstring Conjecture
• Why Greed Works for Shortest Common Superstring Problem
• Why greed works for shortest common superstring problem
• Title not available (Why is that?)
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• More on the complexity of common superstring and supersequence problems
• A \(2_3^2\) superstring approximation algorithm
• Approximating shortest superstring problem using de Bruijn graphs
• Approximating shortest superstrings with constraints
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Lyndon words and short superstrings
• Restricted common superstring and restricted common supersequence
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Greedy shortest common superstring approximation in compact space
• The shortest superstring problem
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Reoptimization of the Shortest Common Superstring Problem
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• Improved length bounds for the shortest superstring problem
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Title not available (Why is that?)
• NC algorithms for finding a maximal set of paths with application to compressing strings
• Parallel and sequential approximation of shortest superstrings
• Title not available (Why is that?)
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

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)