scientific article; zbMATH DE number 2019624

MaRDI QIDQ4440427zbMATH OpenFDO

Authors Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

Publication date 17 December 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2483/24830051.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• The complexity of partition functions

Cited in

(8)

• scientific article; zbMATH DE number 2151247 (Why is no real title available?)
• Multicolor containers, extremal entropy, and counting
• The complexity of partition functions
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Algorithms to approximately count and sample conforming colorings of graphs
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4440427)