Eric Rémila

TCS Journal 2021 Journal Article

influence: A partizan scoring game on graphs

• Eric Duchêne
• Stéphane Gonzalez
• Aline Parreau
• Eric Rémila
• Philippe Solal

We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor's universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

MFCS Conference 2011 Conference Paper

Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence

• Kévin Perrot
• Eric Rémila

Abstract Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. The main interest of sand piles relies in their Self Organized Criticality (SOC), the property that a small perturbation | adding some sand grains | on a fixed configuration has uncontrolled consequences on the system, involving an arbitrary number of grain fall. Physicists L. Kadanoff et al inspire KSPM, a model presenting a sharp SOC behavior, extending the well known Sand Pile Model. In KSPM( D ), we start from a pile of N stacked grains and apply the rule: \(D\! -\! 1\) grains can fall from column i onto the \(D\! -\! 1\) adjacent columns to the right if the difference of height between columns i and \(i\! +\! 1\) is greater or equal to D. This paper develops a formal background for the study of KSPM fixed points. This background, resumed in a finite state word transducer, is used to provide a plain formula for fixed points of KSPM(3).

TCS Journal 2010 Journal Article

Average long-lived binary consensus: Quantifying the stabilizing role played by memory

• Florent Becker
• Sergio Rajsbaum
• Ivan Rapaport
• Eric Rémila

Consider a system composed of n sensors operating in synchronous rounds. In each round an input vector of sensor readings x is produced, where the i -th entry of x is a binary value produced by the i -th sensor. The sequence of input vectors is assumed to be smooth: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging consensus function f. This function returns, in each round, a representative output value v of the sensor readings x. Assuming that at most t entries of the vector can be erroneous, f is required to return a value that appears at least t + 1 times in x. We introduce the definition of instability of the system, which consists in the number of output changes over a random sequence of input vectors. We first design optimal (with respect to the instability measure) consensus systems: D 0 without memory, and D 1 with memory. Then we quantify the gain factor due to memory by computing c n ( t ), the number of decision changes performed by D 0 per decision change performed by D 1.

TCS Journal 2005 Journal Article

Graph encoding of 2 D -gon tilings

• Frédéric Chavanon
• Matthieu Latapy
• Michel Morvan
• Eric Rémila
• Laurent Vuillon

2 D -gon tilings with parallelograms are a model used in physics to study quasicrystals, and they are also important in combinatorics for the study of aperiodic structures. In this paper, we study the graph induced by the adjacency relation between tiles. This relation can been used to encode simply and efficiently 2 D -gon tilings for algorithmic manipulation. We show for example how it can be used to sample random 2 D -gon tilings.

TCS Journal 2004 Journal Article

Domino tilings and related models: space of configurations of domains with holes

• Sébastien Desreux
• Martin Matamala
• Ivan Rapaport
• Eric Rémila

We first prove that the set of domino tilings of a fixed finite figure is a distributive lattice, even in the case when the figure has holes. We then give a geometrical interpretation of the order given by this lattice, using (not necessarily local) transformations called flips. This study allows us to formulate an exhaustive generation algorithm and a uniform random sampling algorithm. We finally extend these results to other types of tilings (calisson tilings, tilings with bicolored Wang tiles).

TCS Journal 2004 Journal Article

Leader election in plane cellular automata, only with left–right global convention

• Codrin Nichitiu
• Christophe Papazian
• Eric Rémila

We give a linear time algorithm to elect a leader. This problem originated in networking and distributed computing research. Given a graph, its vertices represent processors (here finite state machines), and its edges communication lines (here synchronous). The leader election problem consists in finding a protocol for a family of graphs which, upon iteration, distinguishes a vertex, edge or cycle by a special state called leader. Here, the graphs are only required to be connected, and without holes. We describe the algorithm on a special class of planar graphs, prove its correctness and show how it extends to other classes.

TCS Journal 2004 Journal Article

The lattice structure of the set of domino tilings of a polygon

• Eric Rémila

Fix a polygon P with vertical and horizontal sides. We first recall how each tiling of P with dominoes (i. e. rectangles 2×1) can be encoded by a height function. Such an encoding induces a lattice structure on the set T P of the tilings of P. We give some applications of this structure, and we especially describe the order of meet irreducible elements of T P.

TCS Journal 2004 Journal Article

Tilings with trichromatic colored-edges triangles

• Olivier Bodini
• Eric Rémila

This paper studies the tilings with colored-edges triangles constructed on a triangulation of a simply connected orientable surface such that the degree of each interior vertex is even (such as, for (fundamental) example, a part of the triangular lattice of the plane). The constraints are that we only use three colors, all the colors appear in each tile and two tile can share an edge only if this edge has the same color in both tiles. Using previous results on lozenge tilings, we give a linear algorithm of coloration for triangulations of the sphere, or of planar regions with the constraint that the boundary is monochromatic. We define a flip as a shift of colors on a cycle of edges using only two colors. We prove flip connectivity of the set of solutions for the cases seen above (i. e. two tiling are mutually accessible by a sequence of flips), and prove that there is no flip accessibility in the general case where the boundary is not assumed to be monochromatic. Nevertheless, using flips, we obtain a tiling invariant, even in the general case. We finish relaxing the condition, allowing monochromatic triangles. With this hypothesis, some local flips are sufficient for connectivity. We give a linear algorithm of coloration, and strong structural results on the set of solutions.

TCS Journal 2003 Journal Article

Tiling with bars under tomographic constraints

• Christoph Dürr
• Eric Goles
• Ivan Rapaport
• Eric Rémila

We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We present results for particular instances and for a more general problem, while leaving open the initial problem.

SODA Conference 2002 Conference Paper

Tiling groups for Wang tiles

• Cristopher Moore
• Ivan Rapaport
• Eric Rémila

SODA Conference 2000 Conference Paper

An algebraic method to compute a shortest path of local flips between two tilings

• Eric Rémila

SODA Conference 1999 Conference Paper

Compass Permits Leader Election

• Jacques Mazoyer
• Codrin M. Nichitiu
• Eric Rémila

FOCS Conference 1996 Conference Paper

Approximate Strip Packing

• Claire Mathieu
• Eric Rémila

We present an approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. The algorithm finds a packing of n rectangles whose total height is within a factor of (1+/spl epsiv/) of optimal, and has running time polynomial both in n and in 1//spl epsiv/. It is based on a reduction to fractional bin-packing, and can be performed by 5 stages of guillotine cuts.

SODA Conference 1996 Conference Paper

Tiling a Figure Using a Height in a Tree

• Eric Rémila

TCS Journal 1994 Journal Article

A linear algorithm to tile the trapezes with hm and vn

• Eric Rémila

We describe a linear-time algorithm allowing us to know if a planar trapezoidal figure can be tiled by elementary rectangles of type hm (horizontal m × 1 rectangle) and vn (vertical 1 × n rectangle). In addition, the algorithm gives a tiling, when there exists one.