# 教師資料查詢 | 類別: 期刊論文 | 教師: 林莊傑CHUANG-CHIEH LIN(瀏覽個人網頁)

covering problem. Assume that we are given a set of elements~$S$ and two collections $\mathcal{C}_r$ and $\mathcal{C}_b$ of subsets of~$S$, which are called a red collection and a blue collection respectively. We say that a set $A\in\mathcal{C}_r\cup\mathcal{C}_b$ is hit by a subset $S'\subseteq S$ if $A\cap S'\neq\emptyset$.
The red-blue hitting set problem asks for a subset $S'\subseteq S$ such that all sets in the blue collection must be hit by~$S'$, while the number of sets in the red collection hit by $S'$ has to be minimum. This problem is polynomially solvable when the sets in
the blue collection and the red collection have the consecutive ones property. We present a shortest-path-based algorithm for this problem with the consecutive ones property and its time complexity
is $O(|\mathcal{C}_b||S|+|\mathcal{C}_r||S|+|S|^2)$, which improves the previous time bound $O(|\mathcal{C}_{r}||\mathcal{C}_{b}||S|^2)$
by Dom et al. in 2008.

ISSN1872-6119

SDGs
• 優質教育