Improved length bounds for the shortest superstring problem

DOI10.1007/3-540-60220-8_88zbMath1504.68293OpenAlexW1488861257MaRDI QIDQ5057460

Chris Armen, Clifford Stein

Publication date: 16 December 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60220-8_88

Mathematics Subject Classification ID

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

Related Items (4)

The greedy algorithm for shortest superstrings ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Cites Work

• Unnamed Item
• Unnamed Item
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• An efficient algorithm for the all pairs suffix-prefix problem
• Faster implementation of a shortest superstring approximation
• Approximation algorithms for the shortest common superstring problem
• Strongly qth Power–Free Strings
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Fast Pattern Matching in Strings
• Linear approximation of shortest superstrings
• Approximating Shortest Superstrings
• Parallel and sequential approximation of shortest superstrings

This page was built for publication: Improved length bounds for the shortest superstring problem