An efficient fixed-parameter algorithm for 3-Hitting Set |
| |
Authors: | Rolf Niedermeier Peter Rossmanith |
| |
Institution: | a Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076, Tübingen, Germany;b Department of Computer Science, RWTH Aachen, Ahornstr. 55, D-52074, Aachen, Germany |
| |
Abstract: | Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′S with |S′|k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(ck+n) time algorithm with c=d−1+O(d−1). |
| |
Keywords: | NP-complete problem Parameterized complexity Fixed-parameter tractability Exact algorithm 3-Hitting Set |
本文献已被 ScienceDirect 等数据库收录! |
|