• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International journal of management science and engineering management >Efficient network algorithms for two special cases of the weighted set cover problem
【24h】

Efficient network algorithms for two special cases of the weighted set cover problem

机译：加权集覆盖问题的两种特殊情况的高效网络算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the weighted set-cover problem, we are given a finite set 5 and a collection 0 of its subsets. A non-negative weight w_j is associated with each U_j ∈ Ω. The problem is to find a subcollection of 13 with minimum weight so that the union of its sets is equal to S.This problem is a classic NP-hard combinatorial problem. In this paper, we investigate two special cases of the problem that can be solved in strongly polynomial time. The first is the case 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. The second case is where we can sort the elements of S into an order in which the elements of each set of 0 appear consecutively. It is proved that this case reduces to a shortest path problem. In either case, examples are given to illustrate the methods.
机译：在加权集覆盖问题中，我们得到了一个有限集5及其子集的集合0。非负权重w_j与每个U_j∈associated相关联。问题是找到一个最小权重为13的子集合，以使其集合的并集等于S.这个问题是经典的NP-hard组合问题。在本文中，我们研究了可以在强多项式时间内解决的两个特殊情况。第一种情况是任意两个集合的交点为空或完全重叠。显示了如何将这种情况转换为最小切割问题。第二种情况是，我们可以按顺序排列S的元素，使每组0的元素连续出现。事实证明，这种情况可简化为最短路径问题。在这两种情况下，都将通过示例说明这些方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号