4 citations · 7 across the 14 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DM2020
Recoloring graphs of treewidth 2
Valentin Bartier, Nicolas Bousquet, Marc Heinrich
Two (proper) colorings of a graph are adjacent if they differ on exactly one vertex. Jerrum proved that any -coloring of any d-degenerate graph can be transformed into any…
math.CO2020
Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth
Marc Heinrich
The Glauber dynamics on the colourings of a graph is a random process which consists in recolouring at each step a random vertex of a graph with a new colour chosen uniformly at ra…
cs.DS2020
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…