GALaC team seminar

The GALaC team seminar is organized on a regular basis on Friday at 14:00 in the PCRI building (650) at LISN.

Recent and up-coming seminars

Algorithms for the Metric Dimension problem on directed graphs

-- Antoine Dailly (LIMOS, Clermont-Ferrand)

summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem ...

Complexity of positional games

-- Valentin Gledel (Umeå Universitet)

summary: Positional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game, with the rows, columns, and diagonals forming the hyperedges and the ...

The Domino Snake Problem

-- Nicolás Bitar (LISN, Galac)

summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this ...

The fixed-point construction in tilings

-- Antonin Callard (Université de Caen, GREYC)

summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them. It defines the set of colorings of the infinite grid that respects these adjacency constraints. Such a coloring is called a tiling. Given a tileset as input, a question naturally arises: does ...

See all

Translations: fr