2 citations · 3 across the 6 of their papers we have counts for
12 papers
Distributed recoloring of interval and chordal graphs
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich +1
One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the stu…
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…
Partizan Subtraction Games
Eric Duchêne, Marc Heinrich, Richard J. Nowakowski +1
Partizan subtraction games are combinatorial games where two players, say Left and Right, alternately remove a number n of tokens from a heap of tokens, with (resp. $n…
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…
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…
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…