An improved algorithm for the red-blue hitting set problem with the consecutive ones property
學年 99
學期 1
出版（發表）日期 2010-09-30
作品名稱 An improved algorithm for the red-blue hitting set problem with the consecutive ones property
作品名稱（其他語言）
著者 Maw-Shang Chang; Hsiao-Han Chung; Chuang-Chieh Lin
單位
出版者
著錄名稱、卷期、頁數 Information Processing Letters 110(20), pp. 845–848
摘要 Covering problems are important in many applications. In this work, we consider the red-blue hitting set problem, which is a special 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.
關鍵字 Design of algorithms;Covering problem;Hitting set;Consecutive ones property;Shortest path
語言 en_US
ISSN 1872-6119
期刊性質 國外
收錄於 SCI
產學合作
通訊作者 Chuang-Chieh Lin
審稿制度 是
國別 USA
公開徵稿
出版型式 ,電子版,紙本
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/120036 )

SDGS 優質教育