Marc Heinrich

activity

20142022

most citedAsymptotically exact streaming algorithms

4 citations · 7 across the 14 of their papers we have counts for

collaborators

Showing 2018Show all

2 papers · 1 filter

cs.DS2018

The Glauber dynamics for edge-colourings of trees

Michelle Delcourt, Marc Heinrich, Guillem Perarnau

Let $T$ be a tree on $n$ vertices and with maximum degree $Δ$ . We show that for $k \geq Δ + 1$ the Glauber dynamics for $k$ -edge-colourings of $T$ mixes in polynomial time in $n$ . The…

cs.DM2018

Enumerating minimal dominating sets in $K_{t}$ -free graphs and variants

Marthe Bonamy, Oscar Defrain, Marc Heinrich +2

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…

The Glauber dynamics for edge-colourings of trees

Enumerating minimal dominating sets in Kt​-free graphs and variants

Enumerating minimal dominating sets in $K_{t}$ -free graphs and variants