A greedy approximation algorithm for constructing shortest common superstrings

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

Esko Ukkonen, Jorma Tarhio

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, 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, 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