New complexity results for the \(k\)-covers problem

DOI10.1016/j.ins.2011.02.009zbMath1216.68130MaRDI QIDQ545371

Costas S. Iliopoulos, W. F. Smyth, Manal Mohamed

Publication date: 22 June 2011

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2011.02.009

zbMATH Keywords

complexity; regularity; NP-complete; string cover

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R15: Combinatorics on words

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Enhanced string covering, The set of parameterized \(k\)-covers problem, New complexity results for the \(k\)-covers problem, Computing regularities in strings: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New complexity results for the \(k\)-covers problem
• Fast, practical algorithms for computing all the repeats in a string
• Optimal superprimitivity testing for strings
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Detecting leftmost maximal periodicities
• Computing the \(\lambda \)-covers of a string
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• An O(n log n) algorithm for finding all repetitions in a string
• Fast and Practical Algorithms for Computing All the Runs in a String
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Computing the cover array in linear time