New complexity results for the k-covers problem
DOI10.1016/J.INS.2011.02.009zbMATH Open1216.68130OpenAlexW2042481350MaRDI QIDQ545371FDOQ545371
W. F. Smyth, Costas S. Iliopoulos, 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics on words (68R15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- A linear-time approximation algorithm for the weighted vertex cover problem
- Title not available (Why is that?)
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- An O(n log n) algorithm for finding all repetitions in a string
- Computing the cover array in linear time
- Optimal superprimitivity testing for strings
- The complexity of the minimum \(k\)-cover problem
- Detecting leftmost maximal periodicities
- Fast and Practical Algorithms for Computing All the Runs in a String
- New complexity results for the \(k\)-covers problem
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Title not available (Why is that?)
- Fast, practical algorithms for computing all the repeats in a string
- Computing the \(\lambda \)-covers of a string
- Algorithms for computing the \(\lambda\)-regularities in strings
Cited In (12)
- New complexity results for the \(k\)-covers problem
- String Covering: A Survey
- The complexity of the minimum \(k\)-cover problem
- The set of parameterized \(k\)-covers problem
- On the complexity of the k-chain subgraph cover problem
- Computing regularities in strings: a survey
- A new approximation algorithm for \(k\)-set cover problem
- Enhanced string covering
- Experimental evaluation of algorithms for computing quasiperiods
- Quasi-Periodicity in Streams
- A Linear-Time Algorithm for Seeds Computation
- The Minimum Substring Cover Problem
This page was built for publication: New complexity results for the \(k\)-covers problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q545371)
