...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Philosophical magazine: structure and properties of condensed matter >The Multilevel Splitting algorithm for graph colouring with application to the Potts model
【24h】

The Multilevel Splitting algorithm for graph colouring with application to the Potts model

机译：用应用于Potts模型的图形着色的多级分裂算法

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

摘要

Calculating the partition function of the zero-temperature antiferromagnetic model is an important problem in statistical physics. However, an exact calculation is hard since it is strongly connected to a fundamental combinatorial problem of counting proper vertex colourings in undirected graphs, for which an efficient algorithm is not known to exist. Thus, one has to rely on approximation techniques. In this paper, we formulate the problem of the partition function approximation in terms of rare-event probability estimation and investigate the performance of a particle-based algorithm, called Multilevel Splitting, for handling this setting. The proposed method enjoys a provable probabilistic performance guarantee and our numerical study indicates that this algorithm is capable of delivering accurate results using a relatively modest amount of computational resources.
机译：计算零温度反铁磁模型的分区功能是统计物理学中的重要问题。 然而，确切的计算很难，因为它强烈地连接到计算无向图中的适当的顶点着色的基本组合问题，因此不知道存在有效的算法。 因此，一个人必须依赖近似技术。 在本文中，我们在稀有事件概率估计方面制定分区函数近似的问题，并研究称为多级分裂的粒子基算法的性能，用于处理该设置。 所提出的方法享有可提供的概率性能保证，我们的数值研究表明该算法能够使用相对适度的计算资源提供准确的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号