7 citations · 15 across the 8 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DM2018
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…
cs.DM2018
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…
cs.DM2018
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…