Journal article
The complexity of the minimum k-Cover Problem
Journal of Automata, Languages and Combinatorics, Vol.10(5-6), pp.641-653
2005
Abstract
The k-coversproblem (kCP asks us to compute a minimum cardinality set of strings 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 Relaxed Vertex Cover Problem (RVCP), which we show is a special case of Set Cover (SCP). We show further the kCP is equivalent to RVCP restricted to certain classes GXk of graphs that represent all strings x. We discuss approximate solutions of kCP and we state a number of conjectures and open problems related to kCP and GXk.
Details
- Title
- The complexity of the minimum k-Cover Problem
- Authors/Creators
- R. Cole (Author/Creator)C.S. Ilopoulos (Author/Creator)M. Mohamed (Author/Creator)W.F. Smyth (Author/Creator)L. Yang (Author/Creator)
- Publication Details
- Journal of Automata, Languages and Combinatorics, Vol.10(5-6), pp.641-653
- Publisher
- Fakultat fur Informatik
- Identifiers
- 991005542904107891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
- Publisher URL
- http://www.jalc.de/
Metrics
140 File views/ downloads
144 Record Views