A linear time algorithm for shortest cyclic cover of strings

DOI10.1016/j.jda.2016.05.001zbMath1362.68301OpenAlexW2399175009MaRDI QIDQ2628807

Eric Rivals, Bastien Cazaux

Publication date: 15 July 2016

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2016.05.001

zbMATH Keywords

overlapgreedy algorithmEulerian graphsuperstringminimum assignmentshortest cyclic cover of strings

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Can we recover the cover?, Collapsing Superstring Conjecture, Hierarchical overlap graph, Superstring Graph: A New Approach for Genome Assembly, Practical lower and upper bounds for the Shortest Linear Superstring, Superstrings with multiplicities

Cites Work

• Unnamed Item
• Unnamed Item
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• Reverse engineering of compact suffix trees and links: a novel algorithm
• On suffix extensions in suffix trees
• A linear-time algorithm for finding approximate shortest common superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• An efficient algorithm for the all pairs suffix-prefix problem
• Faster implementation of a shortest superstring approximation
• Algorithms on Strings, Trees and Sequences
• Rotations of Periodic Strings and Short Superstrings
• Approximating Shortest Superstring Problem Using de Bruijn Graphs
• Mathematical Foundations of Computer Science 2005
• Lyndon Words and Short Superstrings