New complexity results for the \(k\)-covers problem
From MaRDI portal
Publication:545371
DOI10.1016/j.ins.2011.02.009zbMath1216.68130OpenAlexW2042481350MaRDI QIDQ545371
W. F. Smyth, Manal Mohamed, Costas S. Iliopoulos
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
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Enhanced string covering, String Covering: A Survey, The set of parameterized \(k\)-covers problem, Experimental evaluation of algorithms for computing quasiperiods, Computing regularities in strings: a survey, New complexity results for the \(k\)-covers problem, Quasi-Periodicity in Streams, A Linear-Time Algorithm for Seeds Computation
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
