ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS

DOI10.1142/S0129054105003789MaRDI QIDQ5714671zbMATH OpenOpenAlexFDO

Authors Lili Zhang, F. Blanchet-Sadri

Publication date 15 December 2005

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054105003789

zbMATH Keywords

\(k\)-coversapproximate \(k\)-coversdistance measuresdynamic programmingstring algorithmsstrings

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 7651109
• k-approximate quasiperiodicity under Hamming and edit distance
• The minimum substring cover problem
• scientific article; zbMATH DE number 1003283
• Approximate cover of strings

Cites work

• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An on-line string superprimitivity test
• An optimal algorithm to compute all the covers of a string
• Approximate periods of strings
• Computing the cover array in linear time
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Testing string superprimitivity in parallel

Cited in

(13)

• On approximate enhanced covers under Hamming distance
• Inferring strings from cover arrays
• Algorithms on strings. Translated from the 2001 French original
• The set of parameterized k-covers problem
• NC algorithms for finding a maximal set of paths with application to compressing strings
• Fast Algorithm for Partial Covers in Words
• Fast algorithm for partial covers in words
• The complexity of the minimum k-cover problem
• COVERING A CIRCULAR STRING WITH SUBSTRINGS OF FIXED LENGTH
• String Covering: A Survey
• Approximating the Anticover of a String
• Approximation and fixed parameter algorithms for the approximate cover problem
• The minimum substring cover problem

This page was built for publication: ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS

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