A greedy approximation algorithm for constructing shortest common superstrings

DOI10.1016/0304-3975(88)90167-3zbMath0644.68090MaRDI QIDQ1102756

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 superstring; string-matching; greedy heuristics

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T10: Pattern recognition, speech recognition

68R99: Discrete mathematics in relation to computer science

Related Items

NC algorithms for finding a maximal set of paths with application to compressing strings, Approximating Shortest Superstring Problem Using de Bruijn Graphs, Approximating shortest superstrings with constraints, Parallel and sequential approximation of shortest superstrings, Improved length bounds for the shortest superstring problem, Greedy Shortest Common Superstring Approximation in Compact Space, Practical lower and upper bounds for the Shortest Linear Superstring, Bipartite graphs of small readability, Collapsing Superstring Conjecture, On the readability of overlap digraphs, The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings, A probabilistic PTAS for shortest common superstring, Recognition of overlap graphs, Reoptimization of the shortest common superstring problem, 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, 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, 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, Superstring Graph: A New Approach for Genome Assembly, On the Readability of Overlap Digraphs, On the Shortest Common Superstring of NGS Reads, A Probabilistic PTAS for Shortest Common Superstring, DNA sequencing and string learning, Why Greed Works for Shortest Common Superstring Problem, Reoptimization of the Shortest Common Superstring Problem

Cites Work

• Unnamed Item
• Storing a sparse table
• The greedy travelling salesman's problem
• Fast Pattern Matching in Strings