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

Simple item page
dc.contributor.authorVaisman, R.
dc.contributor.authorRoughan, M.
dc.contributor.authorKroese, D.
dc.date.issued2017
dc.description.abstractCalculating 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.
dc.description.statementofresponsibilityRadislav Vaisman, Matthew Roughan and Dirk P. Kroese
dc.identifier.citationPhilosophical Magazine, 2017; 97(19):1646-1673
dc.identifier.doi10.1080/14786435.2017.1312023
dc.identifier.issn1478-6435
dc.identifier.issn1478-6443
dc.identifier.orcidRoughan, M. [0000-0002-7882-7329]
dc.identifier.urihttp://hdl.handle.net/2440/113554
dc.language.isoen
dc.publisherTaylor & Francis
dc.relation.granthttp://purl.org/au-research/grants/arc/CE140100049
dc.rights© 2017 Informa UK Limited, trading as Taylor & Francis Group
dc.source.urihttps://doi.org/10.1080/14786435.2017.1312023
dc.subjectPartition function; graph colouring; Multilevel Splitting; rare events
dc.titleThe Multilevel Splitting algorithm for graph colouring with application to the Potts model
dc.typeJournal article
pubs.publication-statusPublished

Files

Collections

Mathematical Sciences publications