Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Mueller, Haiko"'
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 line. Two-page book embeddings, i.e., book embeddings into 2 pages, are o
Externí odkaz:
http://arxiv.org/abs/2404.14087
Autor:
Dyer, Martin, Müller, Haiko
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 particular, we consider the case of thick forests, which are a class
Externí odkaz:
http://arxiv.org/abs/2309.01482
Autor:
Heinrich, Marc, Müller, Haiko
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 when G is restricted to the class of strongly orderable graphs, a supercl
Externí odkaz:
http://arxiv.org/abs/2101.01997
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 algorithm exploits the "winding" technology devised by McQuillan [CoRR a
Externí odkaz:
http://arxiv.org/abs/2005.07944
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 class is determined by boundedness of a new graph parameter called bipa
Externí odkaz:
http://arxiv.org/abs/1812.03195
Autor:
Dyer, Martin, Müller, Haiko
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 in cocomparabilty graphs and counting independent sets in comparabilit
Externí odkaz:
http://arxiv.org/abs/1808.09853
Autor:
Dyer, Martin, Müller, Haiko
For any class $\mathcal{C}$ of bipartite graphs, we define quasi-$\cal C$ to be the class of all graphs $G$ such that every bipartition of $G$ belongs to $\cal C$. This definition is motivated by a generalisation of the switch Markov chain on perfect
Externí odkaz:
http://arxiv.org/abs/1801.06494
Autor:
Dyer, Martin, Müller, Haiko
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 of Diaconis, Graham and Holmes. We determine the largest hereditary cla
Externí odkaz:
http://arxiv.org/abs/1705.05790
Autor:
Adler, Isolde, Le, Ngoc Khang, Müller, Haiko, Radovanović, Marko, Trotignon, Nicolas, Vušković, Kristina
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol. 19 no. 1, Graph Theory (October 5, 2017) dmtcs:2575
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 chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhare
Externí odkaz:
http://arxiv.org/abs/1611.09907
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 possible approach to a sampling problem arising in Statistics. We ask: for
Externí odkaz:
http://arxiv.org/abs/1501.07725