Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||The Multilevel Splitting algorithm for graph colouring with application to the Potts model|
|Citation:||Philosophical Magazine, 2017; 97(19):1646-1673|
|Publisher:||Taylor & Francis|
|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|
|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.