Relationship between superstring and compression measures: new insights on the greedy conjecture

DOI10.1016/j.dam.2017.04.017zbMath1388.68302OpenAlexW2615811680WikidataQ123002641 ScholiaQ123002641MaRDI QIDQ1752482

Bastien Cazaux, Eric Rivals

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.04.017

zbMATH Keywords

data compressionapproximation algorithmstringologyassemblygreedy conjectureshortest common superstring problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items

Collapsing Superstring Conjecture, Unnamed Item, Superstrings with multiplicities

Cites Work

• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• The greedy algorithm for shortest superstrings
• On the greedy algorithm for the shortest common superstring problem with reversals
• Why greed works for shortest common superstring problem
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Greedy Conjecture for Strings of Length 4
• The Shortest Superstring Problem
• On the Greedy Superstring Conjecture
• Linear approximation of shortest superstrings
• Approximating Shortest Superstring Problem Using de Bruijn Graphs
• Lyndon Words and Short Superstrings