A linear time algorithm for shortest cyclic cover of strings

DOI10.1016/J.JDA.2016.05.001MaRDI QIDQ2628807zbMATH OpenOpenAlexFDO

Authors Bastien Cazaux, Eric Rivals

Publication date 15 July 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Eulerian graphgreedy algorithmminimum assignmentoverlapshortest cyclic cover of stringssuperstring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Algorithms for Three Versions of the Shortest Common Superstring Problem
• A linear-time algorithm for finding approximate shortest common superstrings
• Linear approximation of shortest superstrings
• Approximating shortest superstrings with constraints
• Superstrings with multiplicities

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• Algorithms on Strings, Trees and Sequences
• An efficient algorithm for the all pairs suffix-prefix problem
• Approximating shortest superstring problem using de Bruijn graphs
• Faster implementation of a shortest superstring approximation
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1263192 (Why is no real title available?)
• Lyndon words and short superstrings
• Mathematical Foundations of Computer Science 2005
• On finding minimal length superstrings
• On suffix extensions in suffix trees
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Rotations of Periodic Strings and Short Superstrings
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings

Cited in

(8)

• Hierarchical overlap graph
• Can we recover the cover?
• Superstring graph: a new approach for genome assembly
• scientific article; zbMATH DE number 2086218 (Why is no real title available?)
• Practical lower and upper bounds for the shortest linear superstring
• Superstrings with multiplicities
• Collapsing Superstring Conjecture
• On a cyclic string-to-string correction problem

This page was built for publication: A linear time algorithm for shortest cyclic cover of strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628807)