Superstrings with multiplicities

DOI10.4230/LIPICS.CPM.2018.21MaRDI QIDQ5140785zbMATH OpenOpenAlexFDO

Authors Bastien Cazaux, Eric Rivals

Publication date 16 December 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.CPM.2018.21

zbMATH Keywords

overlapgreedy algorithmapproximationsubset systemcyclic coverAPX

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Linear approximation of shortest superstrings
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• A 2_3² superstring approximation algorithm
• Approximating shortest superstrings with constraints
• Practical lower and upper bounds for the shortest linear superstring

Cites work

• A linear time algorithm for shortest cyclic cover of strings
• A note on shortest superstrings with flipping
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Greedy in Approximation Algorithms
• Linear approximation of shortest superstrings
• Mathematical Foundations of Computer Science 2005
• On finding minimal length superstrings
• On the greedy algorithm for the shortest common superstring problem with reversals
• On-line construction of suffix trees
• Practical lower and upper bounds for the shortest linear superstring
• Relationship between superstring and compression measures: new insights on the greedy conjecture
• Reoptimization of the shortest common superstring problem
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• The shortest superstring problem

Cited in

(7)

• Superstrings. II
• A linear time algorithm for shortest cyclic cover of strings
• Collapsing Superstring Conjecture
• Superstrings with tensor degrees of freedom
• Practical lower and upper bounds for the shortest linear superstring
• More superstrings from supergravity
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

This page was built for publication: Superstrings with multiplicities

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