00:00:00 / 00:00:00

Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.

Informations sur la vidéo

  • Date de captation 21/07/2022
  • Date de publication 19/11/2025
  • Institut Institut Fourier
  • Langue Anglais
  • Format MP4

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis