5 papers · 1 filter
Interval H-graphs : Recognition and forbidden obstructions
Haiko Müller, Arash Rafiey
We introduce the class of interval -graphs, which is the generalization of interval graphs, particularly interval bigraphs. For a fixed graph with vertices $a_1,a_2,\dots,a_…
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…
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…