5 papers
Counting independent sets in strongly orderable graphs
Marc Heinrich, Haiko Müller
We consider the problem of devising algorithms to count exactly the number of independent sets of a graph G . We show that there is a polynomial time algorithm for this problem whe…
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
Martin Dyer, Marc Heinrich, Mark Jerrum +1
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the al…
Counting independent sets in graphs with bounded bipartite pathwidth
Martin Dyer, Catherine Greenhill, Haiko Müller
We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The c…
Counting Independent Sets in Cocomparability Graphs
Martin Dyer, Haiko Müller
We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques…
Quasimonotone graphs
Martin Dyer, Haiko Müller
For any class of bipartite graphs, we define quasi- to be the class of all graphs such that every bipartition of belongs to . This definition…