شماره ركورد كنفرانس :
4819
عنوان مقاله :
A special case of the weighted set cover problem
پديدآورندگان :
Tayyebi Javad javadtayyebi@birjandut.ac.ir Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran. , Mohammadi Aboumoslem a.mohammadi30@gmail.com Department of Mathematics, Faculty of Sciences, Imam Ali University, Tehran, Iran
كليدواژه :
Set cover , minimum cut , polynomial , time algorithm
عنوان كنفرانس :
سومين همايش بين المللي تركيبيات، رمزنگاري و محاسبات
چكيده فارسي :
A weighted set-cover problem contains a finite set 𝑆 and a collection Ω of its subsets. A nonnegative weight 𝑤_𝑗 is associated with each 𝑈_𝑗 ∈ Ω. The problem is to find a subcollection of ℧ with minimum weight so that the union of its sets is equal to 𝑆. This problem is a classic NP-hard combinatorial problem. In this paper, we investigate a special case of the problem that can be solved in strongly polynomial time where any two sets either have empty intersection or overlap completely. It is shown how this case may be transformed to a minimum cut problem. An example is given to illustrate the method.
