Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > membres

Marc Heinrich


PhD student

Team Graphes, AlgOrithmes et AppLications
Institution Claude Bernard University of Lyon 1
Location Nautibus (Université Lyon1)
E-mail marc.heinrich at
Contact details Publications Thesis
Subject Combinatorial games and extremal structures in graphs.
Abstract Combinatorial games are two players games without randomness nor hidden information. A game is defined by a set of rules. One of the fundamental question is to determine, for a given game the complexity of computing a winning strategy. More precisely, given a starting position, we would like to determine which of the two players has a winning strategy that ensures his victory independently of the other player's moves. ombinatorial game theory has important links with algorithmic complexity:some games are natural sources of hard problems, that is PSPACE-hard or even EXPTIME-hard problems.
There are also relations with combinatorics and algorithms, and in particular online algorithms: an online algorithm can be seen as a two player game, with one player (the algorithm) trying to solve a problem,and the other choosing the order of input to prevent the algorithm from working.Additionally, there are combinatorial games (for example Arc-Kayles, Node-Kayles...) where the two players contribute to building a maximal structure in a graph (e.g. a maximal clique, independent set,...). The complexity of these games is still open.
Advisor Eric Duchene

Last update : 2017-07-06 14:47:30