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

標題: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
語言英文(美國)
ISSN1872-6119
期刊性質國外
收錄於SCI;
產學合作
通訊作者Chuang-Chieh Lin
審稿制度
國別美國
公開徵稿
出版型式,電子版,紙本
相關連結
SDGs
  • 優質教育
Google+ 推薦功能,讓全世界都能看到您的推薦!