Practical lower and upper bounds for the Shortest Linear Superstring
From MaRDI portal
Publication:5140730
DOI10.4230/LIPIcs.SEA.2018.18zbMath1493.68408OpenAlexW2809885410MaRDI QIDQ5140730
Eric Rivals, Bastien Cazaux, Samuel Juhel
Publication date: 16 December 2020
Full work available at URL: https://doi.org/10.4230/lipics.sea.2018.18
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items (4)
All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Collapsing Superstring Conjecture ⋮ Hierarchical overlap graph ⋮ Superstrings with multiplicities
Cites Work
- On the greedy algorithm for the shortest common superstring problem with reversals
- A linear-time algorithm for finding approximate shortest common superstrings
- Why greed works for shortest common superstring problem
- A greedy approximation algorithm for constructing shortest common superstrings
- A note on shortest superstrings with flipping
- Combinatorial algorithms for DNA sequence assembly
- A linear time algorithm for shortest cyclic cover of strings
- The Shortest Superstring Problem
- On the Greedy Superstring Conjecture
- Algorithms for Three Versions of the Shortest Common Superstring Problem
- Efficient string matching
- Algorithms on Strings, Trees and Sequences
- Linear approximation of shortest superstrings
- Approximating Shortest Superstring Problem Using de Bruijn Graphs
- Superstrings with multiplicities
- Mathematical Foundations of Computer Science 2005
- Lyndon Words and Short Superstrings
This page was built for publication: Practical lower and upper bounds for the Shortest Linear Superstring
