[en] In the world derived from the game Tetris, what is a tree? How many leaves can such a tree can have? What happens if instead, we consider the world derived from the game Minecraft? Can we generalise this problem in other worlds? Does there exist an efficient algorithm to determine the maximal number of leaves a tree can have? These are the questions we will answer in this talk, using the point of view of graph theory. To determine the complexity of the problem, we will use some dynamical programming. [fr] Dans le monde dérivé du jeu Tetris, qu'est-ce qu'un arbre ? Combien de feuilles peut-il avoir au maximum ? Et dans le monde de Minecraft ? Peut-on généraliser ce problème à d'autres mondes ? Existe-t-il un algorithme efficace pour déterminer le nombre maximal de feuilles ? C'est à ces questions que nous allons répondre du point de vue de la théorie des graphes. Pour décrire la complexité de ce problème, nous utiliserons la programmation dynamique.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
How to count leaves in the trees from Tetris?
Alternative titles :
[fr] Comment compter les feuilles dans les arbres de Tetris
Publication date :
13 May 2017
Event name :
Quebec Colloquium of the Mathematical Sciences Institute (ISM) students