4 citations · 7 across the 14 of their papers we have counts for
6 papers · 1 filter
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…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…
The Glauber dynamics for edge-colourings of trees
Michelle Delcourt, Marc Heinrich, Guillem Perarnau
Let be a tree on vertices and with maximum degree . We show that for the Glauber dynamics for -edge-colourings of mixes in polynomial time in . The…
Computing maximum cliques in -EPG graphs
Nicolas Bousquet, Marc Heinrich
EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class -EPG is the subclass of EPG graphs where the path on…
Local Conflict Coloring
Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski
Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distr…
Asymptotically exact streaming algorithms
Marc Heinrich, Alexander Munteanu, Christian Sohler
We introduce a new computational model for data streams: asymptotically exact streaming algorithms. These algorithms have an approximation ratio that tends to one as the length of…