Algorithms for Three Versions of the Shortest Common Superstring Problem

DOI10.1007/978-3-642-13509-5_27zbMATH Open1286.68523OpenAlexW1555609656MaRDI QIDQ3575256FDOQ3575256

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

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

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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)