124 citations · 239 across the 28 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
cs.CC2016
Implementations and the independent set polynomial below the Shearer threshold
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The independent set polynomial is important in many areas. For every integer , the Shearer threshold is the value . It is known that for $λ< - λ^*…
cs.CC2016
A complexity trichotomy for approximately counting list H-colourings
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the g…