The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
From MaRDI portal
Publication:4651471
DOI10.1137/S0097539702408363zbMath1105.68114OpenAlexW1966994937MaRDI QIDQ4651471
Steven Kelk, Leslie Ann Goldberg, Mike S. Paterson
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702408363
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)
Related Items (8)
Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ Counting Constraint Satisfaction Problems. ⋮ Systematic scan for sampling colorings ⋮ Unnamed Item ⋮ On systematic scan for sampling H-colorings of the path ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
This page was built for publication: The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random