Working Seminar on Formal Models, Discrete Structures, and Algorithms

Low tree depth decompositions

Patrice Ossona de Mendez (CAMS, CNRS/EHESS, Paris)

When: December 19, 2pm

Where: room G2.91b


We shall introduce low tree-decompositions of structures, and show how they are related to a qualitative jump in the structural properties between classes of sparse structures and classes of dense structures. We also consider some algorithmic applications of these decompositions.