Improved length bounds for the shortest superstring problem

DOI10.1007/3-540-60220-8_88MaRDI QIDQ5057460zbMATH OpenOpenAlexFDO

Authors Chris Armen, Clifford Stein

Publication date 16 December 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60220-8_88

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Approximating Shortest Superstrings
• A 2_3² superstring approximation algorithm
• Sequential and Parallel Approximation of Shortest Superstrings
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• Approximation algorithms for the shortest common superstring problem

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• An efficient algorithm for the all pairs suffix-prefix problem
• Approximating Shortest Superstrings
• Approximation algorithms for the shortest common superstring problem
• Fast Pattern Matching in Strings
• Faster implementation of a shortest superstring approximation
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 828444 (Why is no real title available?)
• Linear approximation of shortest superstrings
• On finding minimal length superstrings
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Parallel and sequential approximation of shortest superstrings
• Strongly qth Power–Free Strings

Cited in

(17)

• A note on shortest superstrings with flipping
• A 2_3² superstring approximation algorithm
• Relationship between superstring and compression measures: new insights on the greedy conjecture
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• The shortest superstring problem
• On the shortest common superstring of NGS reads
• Approximating Shortest Superstrings
• Rotations of Periodic Strings and Short Superstrings
• Approximating shortest superstring problem using de Bruijn graphs
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• Greedy shortest common superstring approximation in compact space
• Mathematical Foundations of Computer Science 2005
• Lyndon words and short superstrings
• Approximation guarantees for shortest superstrings: simpler and better
• The greedy algorithm for shortest superstrings

This page was built for publication: Improved length bounds for the shortest superstring problem

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