• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications - ICCSA 2003 Pt.3 May 18-21, 2003 Montreal, Canada >Improvements to the Helpful-Set Algorithm and a New Evaluation Scheme for Graph-Partitioners
【24h】

Improvements to the Helpful-Set Algorithm and a New Evaluation Scheme for Graph-Partitioners

机译：图集划分帮助集算法的改进和新的评估方案

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

摘要

Graph partitioning is an important subproblem in many applications. To solve it efficiently, the multilevel strategy in combination with a matching algorithm and a local refinement heuristic has proven to be a powerful method, and several libraries exist providing such an implementation. Due to the large involvement of heuristics, the evaluation of these libraries is usually based on experiments. In this paper we show that single experiments are usually not sufficient to judge the quality of an algorithm, since even results obtained for graphs of and identical structure show high variations. This is still true, even if the applied algorithms do not contain any nondeterminism. We propose a scheme that considers these variations and therefore makes evaluations and comparisons of different implementations more meaningful. We have applied this technique to evaluate the improvements of the Helpful-Set 2-partitioning implementation and present the obtained results.
机译：图分区是许多应用程序中的重要子问题。为了有效地解决此问题，已证明将多级策略与匹配算法和局部优化启发式算法相结合是一种有效的方法，并且存在多个提供这种实现的库。由于启发式技术的广泛参与，这些库的评估通常基于实验。在本文中，我们表明，单次实验通常不足以判断算法的质量，因为即使对于结构相同的图获得的结果也显示出很大的差异。即使所应用的算法不包含任何不确定性，也是如此。我们提出了一种考虑这些变化的方案，因此使不同实现的评估和比较更加有意义。我们已经应用了该技术来评估“帮助集2”分区实现的改进，并介绍获得的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号