Greedy algorithms for the shortest common superstring that are asymtotically optimal

DOI10.1007/3-540-61680-2_56MaRDI QIDQ4595487zbMATH OpenOpenAlexFDO

Authors Wojciech Szpankowski, Alan Frieze

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61680-2_56

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• A greedy approximation algorithm for constructing shortest common superstrings
• scientific article; zbMATH DE number 3999290
• On the greedy algorithm for the shortest common superstring problem with reversals
• Approximation algorithms for the shortest common superstring problem
• Reoptimization of the shortest common superstring problem
• Reoptimization of the Shortest Common Superstring Problem
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• A linear-time algorithm for finding approximate shortest common superstrings
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

Cited in

(18)

• A probabilistic PTAS for shortest common superstring
• Approximating shortest superstrings with constraints
• On the Greedy Superstring Conjecture
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Why greed works for shortest common superstring problem
• Viral Genome Compression
• Why Greed Works for Shortest Common Superstring Problem
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Approximating shortest superstrings with constraints
• Shortest common superstrings of random strings
• scientific article; zbMATH DE number 3999290 (Why is no real title available?)
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• Greedy Conjecture for Strings of Length 4
• On the greedy algorithm for the shortest common superstring problem with reversals
• Approximation algorithms for the shortest common superstring problem
• Linear approximation of shortest superstrings
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

This page was built for publication: Greedy algorithms for the shortest common superstring that are asymtotically optimal

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