New complexity results for the \(k\)-covers problem
type: Item
instance of: scholarly article
title: New complexity results for the \(k\)-covers problem
zbMATH Open document ID: 1216.68130
author: Manal Mohamed
author: W. F. Smyth
author: Costas S. Iliopoulos
published in: Information Sciences
publication date: 2011-06-22T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 5911323
zbMATH Keywords: string cover
zbMATH Keywords: regularity
zbMATH Keywords: complexity
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
full work available at URL: j.ins.2011.02.009
OpenAlex ID: W2042481350
cites work: Q4091421
cites work: Optimal superprimitivity testing for strings
cites work: Optimal off-line detection of repetitions in a string
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Fast and Practical Algorithms for Computing All the Runs in a String
cites work: Q5446124
cites work: An optimal algorithm for computing the repetitions in a word
cites work: Q4820869
cites work: Q4198056
cites work: Computing the \(\lambda \)-covers of a string
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Q4934345
cites work: Computing the cover array in linear time
cites work: Detecting leftmost maximal periodicities
cites work: An O(n log n) algorithm for finding all repetitions in a string
cites work: Fast, practical algorithms for computing all the repeats in a string
cites work: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
cites work: Q5506327
DOI: 10.1016/J.INS.2011.02.009
description: scientific article; zbMATH DE number 5911323