Algorithms for Three Versions of the Shortest Common Superstring Problem

DOI10.1007/978-3-642-13509-5_27MaRDI QIDQ3575256zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 26 July 2010

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00742040/file/Algorithms_for_Three_Versions_of_the_Shortest_Common_Superstring_Problem.pdf

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Approximation algorithms for the shortest common superstring problem
• A greedy approximation algorithm for constructing shortest common superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• Reoptimization of the shortest common superstring problem
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• scientific article; zbMATH DE number 3999290
• On the greedy algorithm for the shortest common superstring problem with reversals
• Reoptimization of the Shortest Common Superstring Problem
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• The shortest common superstring problem: average case analysis for both exact and approximate matching

Cited in

(15)

• Shortest common superstrings and scheduling with coordinated starting times
• On the inadequacy of tournament algorithms for the N-SCS problem
• More on the complexity of common superstring and supersequence problems
• Approximation algorithms for the shortest common superstring problem
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• A linear time algorithm for shortest cyclic cover of strings
• Solving 3-superstring in \(3^{n/3}\) time
• The shortest superstring problem
• On the shortest common superstring of NGS reads
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Approximating shortest superstring problem using de Bruijn graphs
• Practical lower and upper bounds for the shortest linear superstring
• Superstrings with multiplicities
• On the greedy algorithm for the shortest common superstring problem with reversals

This page was built for publication: Algorithms for Three Versions of the Shortest Common Superstring Problem

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