A greedy approximation algorithm for constructing shortest common superstrings
From MaRDI portal
An approximation algorithm for the shortest common superstring problem is developed, based on the Knuth-Pratt string-matching procedure and on the greedy heuristics for finding longest Hamiltonian pathsé-game.
Cites work
Cited in
(44)- Why greed works for shortest common superstring problem
- A string-matching interpretation of the equation x^ m y^ n = z^ p
- An efficient algorithm for the all pairs suffix-prefix problem
- A note on shortest superstrings with flipping
- Approximating shortest superstrings with constraints
- Relationship between superstring and compression measures: new insights on the greedy conjecture
- Approximation algorithms for the shortest common superstring problem
- Combinatorial algorithms for DNA sequence assembly
- All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
- Hierarchical overlap graph
- A combinatorial approach to the design of vaccines
- A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
- A linear time algorithm for shortest cyclic cover of strings
- On the readability of overlap digraphs
- Superstring graph: a new approach for genome assembly
- On the Readability of Overlap Digraphs
- On the shortest common superstring of NGS reads
- The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
- A Probabilistic PTAS for Shortest Common Superstring
- scientific article; zbMATH DE number 5074400 (Why is no real title available?)
- DNA sequencing and string learning
- Why Greed Works for Shortest Common Superstring Problem
- Algorithms for Three Versions of the Shortest Common Superstring Problem
- Reoptimization of the Shortest Common Superstring Problem
- A probabilistic PTAS for shortest common superstring
- Recognition of overlap graphs
- Greedy algorithms for the shortest common superstring that are asymtotically optimal
- NC algorithms for finding a maximal set of paths with application to compressing strings
- scientific article; zbMATH DE number 827942 (Why is no real title available?)
- Approximating shortest superstring problem using de Bruijn graphs
- \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
- Parallel and sequential approximation of shortest superstrings
- Improved length bounds for the shortest superstring problem
- Approximating shortest superstrings with constraints
- Practical lower and upper bounds for the shortest linear superstring
- Greedy shortest common superstring approximation in compact space
- Collapsing Superstring Conjecture
- Bipartite graphs of small readability
- Reoptimization of the shortest common superstring problem
- Approximation guarantees for shortest superstrings: simpler and better
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- On the greedy algorithm for the shortest common superstring problem with reversals
- A linear-time algorithm for finding approximate shortest common superstrings
- Optimal prefix and suffix queries on texts
This page was built for publication: A greedy approximation algorithm for constructing shortest common superstrings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102756)
