On the Greedy Superstring Conjecture

DOI10.1137/040619144MaRDI QIDQ3440268zbMATH OpenOpenAlexWikidataFDO

Authors Maik Weinard, Georg Schnitger

Publication date 22 May 2007

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/040619144

zbMATH Keywords

approximationDNA fragment assemblyperformance analysissuperstring

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Linear approximation of shortest superstrings
• scientific article; zbMATH DE number 3999290
• Greedy algorithms for the shortest common superstring that are asymtotically optimal

Cited in

(7)

• Relationship between superstring and compression measures: new insights on the greedy conjecture
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• Analysis of heuristics.
• Practical lower and upper bounds for the shortest linear superstring
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM

This page was built for publication: On the Greedy Superstring Conjecture

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