2 citations · 3 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
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…
A polynomial version of Cereceda's conjecture
Nicolas Bousquet, Marc Heinrich
Let and be such that . Consider two -colourings of a -degenerate graph . Can we transform one into the other by recolouring one vertex at each step whil…
Enumerating minimal dominating sets in -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 switch operators and push-the-button games: a sequential compound over rulesets
Eric Duchene, Marc Heinrich, Urban Larsson +1
We study operators that combine combinatorial games. This field was initiated by Sprague-Grundy (1930s), Milnor (1950s) and Berlekamp-Conway-Guy (1970-80s) via the now classical di…