New complexity results for the \(k\)-covers problem
From MaRDI portal
Publication:545371
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
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
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