7 citations · 15 across the 8 of their papers we have counts for
14 papers
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_…
A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Mueller, Sebastian Ordyniak +2
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that lin…
Thick Forests
Martin Dyer, Haiko Müller
We consider classes of graphs, which we call thick graphs, that have the vertices of a corresponding thin graph replaced by cliques and the edges replaced by cobipartite graphs In…
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 weighted independent sets beyond the permanent
Martin Dyer, Mark Jerrum, Haiko Muller +1
Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition…
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…
Counting perfect matchings and the switch chain
Martin Dyer, Haiko Müller
We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain o…
On rank-width of even-hole-free graphs
Isolde Adler, Ngoc Khang Le, Haiko Müller +3
We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because cho…
On the switch Markov chain for perfect matchings
Martin Dyer, Mark Jerrum, Haiko Müller
We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possi…
NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph
Carl Feghali, Faisal N. Abu-Khzam, Haiko Müller
This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. T…
Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
Faisal N. Abu-Khzam, Carl Feghali, Haiko Müller
A graph is \emph{partitionable} if there exists a partition of such that induces a disjoint union of cliques and induces a triangle-free graph.…