4 citations · 7 across the 14 of their papers we have counts for
20 papers
Short and local transformations between ()-colorings
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich +1
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring to a target coloring . Adding the constraint that each pair of cons…
Wealth distribution in villages. Transition from socialism to capitalism in view of exhaustive wealth data and a master equation approach
István Gere, Szabolcs Kelemen, Tamás S. Biró +1
Socio-economic inequalities derived from an exhaustive wealth distribution is studied in a closed geographical region from Transylvania (Romania). Exhaustive wealth data is compute…
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…
On a recolouring version of Hadwiger's conjecture
Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne +1
We prove that for any , for any large enough , there is a graph that admits no -minor but admits a -colouring that is "frozen" wi…
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…
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…
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…
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…
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…
A generalization of Arc-Kayles
Antoine Dailly, Valentin Gledel, Marc Heinrich
The game Arc-Kayles is played on an undirected graph with two players taking turns deleting an edge and its endpoints from the graph. We study a generalization of this game, Weight…
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…
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…
A probabilistic Hadwiger-Nelson problem
Thomas Bourgeat, Marc Heinrich, Paul Melotti +1
If you color a table using k colors, and throw a needle randomly on it, for some proper definition, you get a certain probability that the endpoints will fall on different colors.…
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…
New Algorithmic Approaches to Point Constellation Recognition
Thomas Bourgeat, Julien Bringer, Herve Chabanne +7
Point constellation recognition is a common problem with many pattern matching applications. Whilst useful in many contexts, this work is mainly motivated by fingerprint matching.…