A linear-time algorithm for finding approximate shortest common superstrings

DOI10.1007/BF01840391zbMath0696.68075OpenAlexW2002148379MaRDI QIDQ911299

Esko Ukkonen

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840391

zbMATH Keywords

approximation algorithmHamiltonian pathlinear-time algorithmshortest common superstringgreedy heuristics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items (13)

A linear time algorithm for shortest cyclic cover of strings ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ All-pairs suffix/prefix in optimal time using Aho-Corasick space ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Analysis of the Period Recovery Error Bound ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ An efficient algorithm for the all pairs suffix-prefix problem ⋮ THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW ⋮ About the design of oligo-chips ⋮ Optimal prefix and suffix queries on texts ⋮ Hierarchical overlap graph ⋮ Practical lower and upper bounds for the Shortest Linear Superstring

Cites Work

• Unnamed Item
• Unnamed Item
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Efficient string matching
• Fast Pattern Matching in Strings

This page was built for publication: A linear-time algorithm for finding approximate shortest common superstrings