Show simple item record

dc.contributor.authorIliopoulos, Costas
dc.contributor.authorMohamed, M.
dc.contributor.authorSmyth, William
dc.date.accessioned2017-01-30T11:45:21Z
dc.date.available2017-01-30T11:45:21Z
dc.date.created2012-02-27T20:01:04Z
dc.date.issued2011
dc.identifier.citationIliopoulos, Costas S. and Mohamed, Manal and Smyth, W.F. 2011. New complexity results for the k-covers problem. Information Sciences. 181 (12): pp. 2571-2575.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/14681
dc.identifier.doi10.1016/j.ins.2011.02.009
dc.description.abstract

The k-covers problem (kCP) asks us to compute a minimum cardinality set of strings of given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3-SAT, that the k-covers problem is NP-complete. In this paper we introduce a new problem, that we call the k-bounded relaxed vertex cover problem (RVCPk), which we show is equivalent to k-bounded set cover (SCPk). We show further that kCP is a special case of RVCPk restricted to certain classes Gx,k of graphs that represent all strings x. Thus a minimum k-cover can be approximated to within a factor k in polynomial time. We discuss approximate solutions of kCP, and we state a number of conjectures and open problems related to kCP and Gx,k.

dc.publisherElsevier Inc
dc.subjectNP-complete
dc.subjectComplexity
dc.subjectString
dc.subjectRegularity
dc.subjectCover
dc.titleNew complexity results for the k-covers problem
dc.typeJournal Article
dcterms.source.volume181
dcterms.source.number12
dcterms.source.startPage2571
dcterms.source.endPage2575
dcterms.source.issn00200255
dcterms.source.titleInformation Sciences
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusFulltext not available


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record