Lyndon Words and Short Superstrings
From MaRDI portal
Publication:5741777
DOI10.1137/1.9781611973105.69zbMath1422.68332arXiv1205.6787OpenAlexW2950973021MaRDI QIDQ5741777
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1205.6787
Related Items (18)
A linear time algorithm for shortest cyclic cover of strings ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Parameterized complexity of superstring problems ⋮ A probabilistic PTAS for shortest common superstring ⋮ The “Runs” Theorem ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Dynamic and internal longest common substring ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Collapsing Superstring Conjecture ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ 2D Lyndon words and applications ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence ⋮ Practical lower and upper bounds for the Shortest Linear Superstring ⋮ Longest Lyndon Substring After Edit
This page was built for publication: Lyndon Words and Short Superstrings