CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM

DOI10.1142/S0129054105003777zbMath1105.68026OpenAlexW1982157147MaRDI QIDQ5714670

Maik Weinard, Uli Laube

Publication date: 15 December 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105003777

zbMATH Keywords

performance ratiogreedy heuristicshortest superstring

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (2)

All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Collapsing Superstring Conjecture

Uses Software

• SoPlex

Cites Work

• Approximation algorithms for the shortest common superstring problem
• Proof verification and the hardness of approximation problems
• DNA sequencing and string learning
• Linear approximation of shortest superstrings
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

This page was built for publication: CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM