...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Exact algorithms for dominating set
【24h】

Exact algorithms for dominating set

机译：支配集的精确算法

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

摘要

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969n) time and polynomial space algorithm.
机译：测量和征服方法已被证明是分析诸如组合集和独立集之类组合问题的精确算法的强大工具。本文使用这种方法来获得更快的精确控制集算法。我们通过考虑一系列分支和约简算法来获得该算法。该系列是一个迭代过程的结果，其中对该系列中具有度量和征服的算法进行数学分析会导致凸或准凸编程问题。通过计算机来解决该问题的解决方案不仅限制了算法的运行时间，而且还可以指示在哪里寻找新的归约规则，通常会给出新的，可能更快的算法。结果，我们获得了O（1.4969n）时间和多项式空间算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号