The complexity of the minimum k-cover problem

MaRDI QIDQ5446124zbMATH OpenFDO

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

Publication date 6 March 2008

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)

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

Cited in

(20)

• The complexity of the vertex-minor problem
• Efficient Computation of 2-Covers of a String.
• Computing regularities in strings: a survey
• scientific article; zbMATH DE number 1855660 (Why is no real title available?)
• Approximation and fixed parameter algorithms for the approximate cover problem
• Enhanced string covering
• Covering a set with arithmetic progressions is NP-complete
• New complexity results for the \(k\)-covers problem
• The set of parameterized \(k\)-covers problem
• The complexity of minimum difference cover
• String Covering: A Survey
• scientific article; zbMATH DE number 5936584 (Why is no real title available?)
• The minimum substring cover problem
• Minimum constellation covers: hardness, approximability and polynomial cases
• String covering with optimal covers
• Quasi-Periodicity in Streams
• Experimental evaluation of algorithms for computing quasiperiods
• Approximating the Anticover of a String
• The Minimum Substring Cover Problem
• Solving the minimum string cover problem

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)