All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

DOI10.1007/978-3-030-86692-1_6MaRDI QIDQ2146125zbMATH OpenOpenAlexFDO

Authors Maksim S. Nikolaev

Publication date 15 June 2022

Full work available at URL https://arxiv.org/abs/2102.05579

zbMATH Keywords

approximationgreedy algorithmsgreedy conjectureshortest common superstringsuperstring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• On the greedy algorithm for the shortest common superstring problem with reversals
• A greedy approximation algorithm for constructing shortest common superstrings
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• scientific article; zbMATH DE number 3999290
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Approximation algorithms for the shortest common superstring problem
• Why Greed Works for Shortest Common Superstring Problem
• Why greed works for shortest common superstring problem
• Reoptimization of the shortest common superstring problem

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• An Eulerian path approach to DNA fragment assembly
• Approximating shortest superstring problem using de Bruijn graphs
• Approximation algorithms for the shortest common superstring problem
• Collapsing Superstring Conjecture
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Greedy Conjecture for Strings of Length 4
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• Linear approximation of shortest superstrings
• Lyndon words and short superstrings
• On finding minimal length superstrings
• On the Greedy Superstring Conjecture
• Practical lower and upper bounds for the shortest linear superstring
• Superstrings with multiplicities
• The greedy algorithm for shortest superstrings
• The shortest superstring problem

Cited in

(2)

• Why greed works for shortest common superstring problem
• Greedy algorithms for the shortest common superstring that are asymtotically optimal

This page was built for publication: All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

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