An improved algorithm for the red-blue hitting set problem with the consecutive ones property
學年 97
學期 2
發表日期 2009-04-24
作品名稱 An improved algorithm for the red-blue hitting set problem with the consecutive ones property
作品名稱（其他語言）
著者 Maw-Shang Chang; Hsiao-Han Chung; Chuang-Chieh Lin
作品所屬單位
出版者
會議名稱 Workshop on Combinatorial Mathematics and Computation Theory
會議地點 Chiayi, Taiwan
摘要 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 Cr and Cb of subsets of S, which are called a red collection and a blue collection respectively. We say that a set A ∈ C_r ∪ C_b is hit by a subset S′ ⊆ S if A∩S′ = ∅. The red-blue hitting set problem asks for a subset S′ ⊆ 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(|C_b||S| + |C_r||S| + |S|^2), which improves the previous time bound O(|C_r||C_b||S|^2) by Dom et al.
關鍵字 Covering problem;Hitting set; Consecutive ones property; Shortest path
語言 zh_TW
收錄於
會議性質 國內
校內研討會地點 無
研討會時間 20090424~20090425
通訊作者
國別 TWN
公開徵稿
出版型式
出處
相關連結

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

SDGS 優質教育