...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computers & operations research >Heuristic and exact algorithms for the spanning tree detection problem
【24h】

Heuristic and exact algorithms for the spanning tree detection problem

机译：生成树检测问题的启发式精确算法

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

摘要

Given an integer α and an undirected graph with edges associated with integer weights, the spanning tree detection problem (STDP) is to find, if one exists, a spanning tree of weight α. STDP is NP-hard. In this paper we develop both approximate and exact algorithms to solve STDP. Approximate algorithm consists of a greedy method to construct an initial spanning tree quickly, and a local search method that improves the weight of the tree successively toward α. To solve STDP completely, we take a 'divide and conquer' approach and develop an exact algorithm. These algorithms are implemented in C language and we conduct some numerical tests to evaluate the performance of the developed algorithms for various types and sizes of instances. In most cases, we are able to solve STDPs with up to 1000 nodes in less than a few seconds. Moreover, to solve harder instances we try tabu search as well, and mention how the developed algorithm can be modified to list up all the spanning trees of weight α.
机译：给定一个整数α和一个与整数权重关联的边的无向图，生成树检测问题（STDP）将查找权重α的生成树（如果存在）。 STDP是NP硬式的。在本文中，我们开发了近似算法和精确算法来求解STDP。近似算法包括一个贪婪方法和一个快速生成初始生成树的局部搜索方法，以及一个局部搜索方法，该方法逐步提高了树对α的权重。为了完全解决STDP，我们采用“分而治之”的方法，并开发出一种精确的算法。这些算法以C语言实现，我们进行了一些数值测试，以评估针对各种类型和大小的实例开发的算法的性能。在大多数情况下，我们能够在不到几秒钟的时间内解决多达1000个节点的STDP。此外，为了解决更困难的情况，我们也尝试禁忌搜索，并提到如何修改开发的算法以列出所有权重为α的生成树。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号