scientific article; zbMATH DE number 2019624

zbMATH Open1028.68098MaRDI QIDQ4440427FDOQ4440427

Martin Dyer, Mark Jerrum, Leslie Ann Goldberg

Publication date: 17 December 2003

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

Title of this publication is not available (Why is that?)

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

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)

Cited In (7)

• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Counting and sampling \(H\)-colourings
• Title not available (Why is that?)
• Algorithms to approximately count and sample conforming colorings of graphs
• The complexity of partition functions
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• 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)