A greedy approximation algorithm for constructing shortest common superstrings

DOI10.1016/0304-3975(88)90167-3MaRDI QIDQ1102756zbMATH OpenOpenAlexFDO

Authors Jorma Tarhio, Esko Ukkonen

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

zbMATH Keywords

shortest common superstringstring-matchinggreedy heuristics

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Fast Pattern Matching in Strings
• Storing a sparse table
• The greedy travelling salesman's problem

Cited in

(43)

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

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)