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

greedy heuristicsshortest common superstringstring-matching

Mathematics Subject Classification ID

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

Cites work

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

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)