Greedy Shortest Common Superstring Approximation in Compact Space

DOI10.1007/978-3-319-67428-5_1zbMath1454.68195arXiv1707.07727OpenAlexW2738886857MaRDI QIDQ5150914

Jarno Alanko, Tuukka Norri

Publication date: 16 February 2021

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.07727

zbMATH Keywords

Burrows-Wheeler transformcompact spaceBWTshortest common superstringgreedy approximationspace-efficientSCS

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (1)

Compressed Multiple Pattern Matching

Cites Work

• The greedy algorithm for shortest superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• A linear-time algorithm for a special case of disjoint set union
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Approximation algorithms for the shortest common superstring problem
• Linear time construction of compressed text indices in compact space
• Lyndon Words and Short Superstrings
• Unnamed Item

This page was built for publication: Greedy Shortest Common Superstring Approximation in Compact Space