Covering a Set with Arithmetic Progressions is NP-Complete

Simple item page
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:33Zen
dc.date.available2013-06-19T14:36:33Zen
dc.date.issued1989en
dc.description.abstractThis paper defines a new class of set covering problems in which the subsets are implicitly derived from the properties of the set elements. In particular, the set elements are integers and the subsets are finite arithmetic progressions. Both minimum cover and exact cover problems are defined. Both problems are shown to be NP-Complete.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000162/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000162/01/TR-89-25.pdfen
dc.identifier.trnumberTR-89-25en
dc.identifier.urihttp://hdl.handle.net/10919/19566en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleCovering a Set with Arithmetic Progressions is NP-Completeen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-89-25.pdf
Size:
431.51 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports