Conference presentation
New complexity results for the k-covers problem
15th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2004 (Ballina Beach Resort, New South Wales, 07/07/2004–09/07/2004)
2004
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 Related Vertex Cover Problem (RVCP), which we show is a special case of Set Cover (SCP). We show further that kCP is equivalent to RVCP restricted to certain classes Gx.k 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 Gx.k
Details
- Title
- New complexity results for the k-covers problem
- Authors/Creators
- C.S. Ilopoulos (Author/Creator)M. Mohamed (Author/Creator)W.F. Smyth (Author/Creator)
- Conference
- 15th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2004 (Ballina Beach Resort, New South Wales, 07/07/2004–09/07/2004)
- Identifiers
- 991005544673507891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference presentation
Metrics
135 File views/ downloads
31 Record Views