A greedy approximation algorithm for constructing shortest common superstrings
From MaRDI portal
Publication:1102756
DOI10.1016/0304-3975(88)90167-3zbMath0644.68090OpenAlexW2090223576MaRDI QIDQ1102756
Publication date: 1988
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(88)90167-3
Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Discrete mathematics in relation to computer science (68R99)
Related Items (37)
On the readability of overlap digraphs ⋮ DNA sequencing and string learning ⋮ Approximating shortest superstrings with constraints ⋮ A linear time algorithm for shortest cyclic cover of strings ⋮ Parallel and sequential approximation of shortest superstrings ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ Improved length bounds for the shortest superstring problem ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ A Probabilistic PTAS for Shortest Common Superstring ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ On the Readability of Overlap Digraphs ⋮ A probabilistic PTAS for shortest common superstring ⋮ Recognition of overlap graphs ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Reoptimization of the shortest common superstring problem ⋮ A linear-time algorithm for finding approximate shortest common superstrings ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Collapsing Superstring Conjecture ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ A string-matching interpretation of the equation \(x^ m y^ n = z^ p\) ⋮ An efficient algorithm for the all pairs suffix-prefix problem ⋮ NC algorithms for finding a maximal set of paths with application to compressing strings ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ A note on shortest superstrings with flipping ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Optimal prefix and suffix queries on texts ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ Hierarchical overlap graph ⋮ Approximating shortest superstrings with constraints ⋮ Bipartite graphs of small readability ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ Superstring Graph: A New Approach for Genome Assembly ⋮ Why greed works for shortest common superstring problem ⋮ A combinatorial approach to the design of vaccines ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem ⋮ Practical lower and upper bounds for the Shortest Linear Superstring
Cites Work
This page was built for publication: A greedy approximation algorithm for constructing shortest common superstrings
