Collapsing Superstring Conjecture
From MaRDI portal
Publication:5875478
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.26OpenAlexW2977302951MaRDI QIDQ5875478
Alexander Logunov, Maksim S. Nikolaev, Alexander Golovnev, Ivan Mihajlin, Alexander S. Kulikov
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1809.08669
Related Items (1)
Uses Software
Cites Work
- A finite-difference sieve to count paths and cycles by length
- The greedy algorithm for shortest superstrings
- A greedy approximation algorithm for constructing shortest common superstrings
- On finding minimal length superstrings
- Dynamic programming meets the principle of inclusion and exclusion
- Faster and simpler approximation of stable matchings
- Relationship between superstring and compression measures: new insights on the greedy conjecture
- Approximation algorithms for the shortest common superstring problem
- Hierarchical overlap graph
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- A linear time algorithm for shortest cyclic cover of strings
- Greedy Conjecture for Strings of Length 4
- The Shortest Superstring Problem
- Dynamic Programming Treatment of the Travelling Salesman Problem
- P-Complete Approximation Problems
- Linear approximation of shortest superstrings
- An Eulerian path approach to DNA fragment assembly
- Approximating Shortest Superstring Problem Using de Bruijn Graphs
- Practical lower and upper bounds for the Shortest Linear Superstring
- Superstrings with multiplicities
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- The traveling-salesman problem and minimum spanning trees: Part II
- CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
- Lyndon Words and Short Superstrings
This page was built for publication: Collapsing Superstring Conjecture
