Lyndon Words and Short Superstrings

DOI10.1137/1.9781611973105.69zbMath1422.68332arXiv1205.6787OpenAlexW2950973021MaRDI QIDQ5741777

Marcin Mucha

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

Mathematics Subject Classification ID

Combinatorics on words (68R15) Approximation algorithms (68W25) Algorithms on strings (68W32)

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