An improved algorithm for the red-blue hitting set problem with the consecutive ones property

作者：Chang Maw Shang; Chung Hsiao Han; Lin Chuang Chieh^*

来源：Information Processing Letters, 2010, 110(20): 845-848.

DOI：10.1016/j.ipl.2010.07.010

• Design of algorithms
• Covering problem
• Hitting set
• Consecutive ones property
• Shortest path

Let S be a set of elements. We say that a collection C of subsets of S has the consecutive ones property if there exist a linear order on S and a 0-1 matrix M, where M-ij = 1 if and only if the jth element is in the ith set in C. such that all l's appear consecutively in each row of M. A set X is an element of C is hit by a subset S' subset of S if X boolean AND S' not equal 0. Let C-r (red collection) and C-b (blue collection) be two collections of subsets of S respectively. The red-blue hitting set problem asks for a subset S' subset of S such that all sets in the blue collection are hit by S', while the number of sets in the red collection hit by S' has to be minimum. We present a shortest-path based algorithm with time complexity O(vertical bar C-b parallel to S vertical bar + vertical bar C-r parallel to S vertical bar + vertical bar S vertical bar(2)) for this problem with C-r boolean OR C-b having the consecutive ones property, which improves the previous time bound O(vertical bar C-r parallel to C-b parallel to S vertical bar(2)) by Dom et al. (2008) [8].

• 出版日期2010-9-30