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

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

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)

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

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)