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

DOI10.1007/978-3-030-86692-1_6OpenAlexW3203673063MaRDI QIDQ2146125

Maksim S. Nikolaev

Publication date: 15 June 2022

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

zbMATH Keywords

approximationsuperstringgreedy algorithmsgreedy conjectureshortest common superstring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• The greedy algorithm for shortest superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Approximation algorithms for the shortest common superstring problem
• Greedy Conjecture for Strings of Length 4
• The Shortest Superstring Problem
• On the Greedy Superstring Conjecture
• Linear approximation of shortest superstrings
• An Eulerian path approach to DNA fragment assembly
• Approximating Shortest Superstring Problem Using de Bruijn Graphs
• Practical lower and upper bounds for the Shortest Linear Superstring
• Superstrings with multiplicities
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Lyndon Words and Short Superstrings
• Collapsing Superstring Conjecture

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