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
• Publication:4725747
• 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

(13)

• A linear time algorithm for shortest cyclic cover of strings
• More on the complexity of common superstring and supersequence problems
• Approximating shortest superstring problem using de Bruijn graphs
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Practical lower and upper bounds for the shortest linear superstring
• On the shortest common superstring of NGS reads
• Superstrings with multiplicities
• On the greedy algorithm for the shortest common superstring problem with reversals
• Solving 3-superstring in \(3^{n/3}\) time
• Approximation algorithms for the shortest common superstring problem
• The shortest 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

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)