On the greedy algorithm for the shortest common superstring problem with reversals

DOI10.1016/j.ipl.2015.11.015zbMath1347.68376arXiv1511.08431OpenAlexW2176235320MaRDI QIDQ903196

Jakub Radoszewski, Wojciech Rytter, Gabriele Fici, Tomasz Kociumaka, Tomasz Walen

Publication date: 5 January 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08431

zbMATH Keywords

greedy algorithmanalysis of algorithmsshortest common superstringreversal

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Algorithms on strings (68W32)

Related Items (4)

On the Shortest Common Superstring of NGS Reads ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ Practical lower and upper bounds for the Shortest Linear Superstring ⋮ Superstrings with multiplicities

Cites Work

• The greedy algorithm for shortest superstrings
• 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
• On finding minimal length superstrings
• A note on shortest superstrings with flipping
• Approximating shortest superstrings with constraints
• Approximation algorithms for the shortest common superstring problem
• Combinatorial algorithms for DNA sequence assembly
• The Shortest Superstring Problem
• Restricted Common Superstring and Restricted Common Supersequence
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Linear approximation of shortest superstrings
• Lyndon Words and Short Superstrings

This page was built for publication: On the greedy algorithm for the shortest common superstring problem with reversals