The complexity of the minimum k-cover problem

zbMATH Open1136.68618MaRDI QIDQ5446124FDOQ5446124

Authors: Costas S. Iliopoulos, Manal Mohamed, W. F. Smyth, Lu Yang, Richard Cole 

Publication date: 6 March 2008

Recommendations

• New complexity results for the \(k\)-covers problem
• The minimum substring cover problem
• The Minimum Substring Cover Problem
• Solving the minimum string cover problem
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS

zbMATH Keywords

vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cited In (23)

• New complexity results for the \(k\)-covers problem
• String Covering: A Survey
• Efficient Computation of 2-Covers of a String.
• The set of parameterized \(k\)-covers problem
• Computing regularities in strings: a survey
• The complexity of minimum difference cover
• Minimum constellation covers: hardness, approximability and polynomial cases
• String covering with optimal covers
• Title not available (Why is that?)
• Solving the minimum string cover problem
• The complexity of computing minimal unidirectional covering sets
• Enhanced string covering
• Experimental evaluation of algorithms for computing quasiperiods
• The minimum substring cover problem
• Quasi-Periodicity in Streams
• A Linear-Time Algorithm for Seeds Computation
• The Minimum Substring Cover Problem
• The complexity of the vertex-minor problem
• Covering a set with arithmetic progressions is NP-complete
• Approximating the Anticover of a String
• Title not available (Why is that?)
• Approximation and fixed parameter algorithms for the approximate cover problem
• Covering problems for partial words and for indeterminate strings

This page was built for publication: The complexity of the minimum \(k\)-cover problem

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