Parallel and sequential approximation of shortest superstrings

DOI10.1007/3-540-58218-5_9zbMath1502.68369OpenAlexW1501313444MaRDI QIDQ5056169

Marek Piotrów, Artur Czumaj, Leszek Gąsieniec, Wojciech Rytter

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_9

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (5)

Improved length bounds for the shortest superstring problem ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Fast RNC and NC algorithms for maximal path sets ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Approximation algorithms for the shortest common superstring problem
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems

This page was built for publication: Parallel and sequential approximation of shortest superstrings