Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: The Multilevel Splitting algorithm for graph colouring with application to the Potts model
Author: Vaisman, R.
Roughan, M.
Kroese, D.
Citation: Philosophical Magazine, 2017; 97(19):1646-1673
Publisher: Taylor & Francis
Issue Date: 2017
ISSN: 1478-6435
Statement of
Radislav Vaisman, Matthew Roughan and Dirk P. Kroese
Abstract: 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 rareevent 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.
Keywords: Partition function; graph colouring; Multilevel Splitting; rare events
Rights: © 2017 Informa UK Limited, trading as Taylor & Francis Group
DOI: 10.1080/14786435.2017.1312023
Grant ID:
Appears in Collections:Aurora harvest 3
Mathematical Sciences publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.