The complexity of choosing an H -colouring (nearly) uniformly at random

DOI10.1145/509907.509917zbMath1192.68898OpenAlexW2102514254MaRDI QIDQ3579223

Steven Kelk, Leslie Ann Goldberg, Mike S. Paterson

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509917

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

Counting and sampling \(H\)-colourings ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ The complexity of partition functions

This page was built for publication: The complexity of choosing an H -colouring (nearly) uniformly at random