Show simple item record

dc.contributor.authorIliopoulos, Costas
dc.contributor.authorMohamed, M.
dc.contributor.authorSmyth, Bill
dc.contributor.editorPeter Eades
dc.contributor.editorSeokhee Hong
dc.date.accessioned2017-01-30T15:22:32Z
dc.date.available2017-01-30T15:22:32Z
dc.date.created2010-04-01T20:02:07Z
dc.date.issued2004
dc.identifier.citationIliopoulos, Costas and Mohamed, Manal and Smyth, W. F. 2004. New complexity results for the k-covers problem, in Eades, P. and Hong, S. (ed), 15th Australian Workshop on Combinatorial Algorithms (AWOCA), pp. 141-147. Ballina, Australia: Australian Computer Society.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/45670
dc.description.abstract

The k-covers problem (kCP) asks us to compute a minimum cardinality set of stringsof 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.publisherAustralian Computer Society
dc.subjectNP-complete
dc.subjectcover
dc.subjectcomplexity
dc.subjectstring
dc.subjectregularity
dc.titleNew complexity results for the k-covers problem
dc.typeConference Paper
dcterms.source.startPage141
dcterms.source.endPage147
dcterms.source.titleProceedings of the 15th Australian workshop on combinatorial algorithms (AWOCA)
dcterms.source.seriesProceedings of the 15th Australian workshop on combinatorial algorithms (AWOCA)
dcterms.source.conference15th Australian Workshop on Combinatorial Algorithms (AWOCA)
dcterms.source.conference-start-dateJul 7 2004
dcterms.source.conferencelocationBallina, Australia
dcterms.source.placeAustralia
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusOpen access
curtin.facultyCurtin Business School
curtin.facultyThe Digital Ecosystems and Business Intelligence Institute (DEBII)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record