• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

    UE Graph and discrete structures

    • Niveau d'étude

      Bac +5

    • ECTS

      3 crédits

    • Crédits ECTS Echange

      3.0

    • Composante

      UFR IM2AG (informatique, mathématiques et mathématiques appliquées)

    • Période de l'année

      Automne (sept. à dec./janv.)

    Description

    The aim of this course is to learn how to use the structure of graphs and other discrete objects to obtain general results on them, and in particular efficient algorithms solving important problems.

    We will cover the following topics:

    • Structural Graph Theory: we will study the structure of important graph classes with nice algorithmic properties (planar graphs, interval graphs, comparability graphs, ...) and show several concrete problems that can be solved thanks to their structural properties.
    • Graph Drawing: with the rise of Big Data, representing huge data sets is a fundamental challenge. Efficient ways to represent large graphs will be presented.
    • Codes: we will see various codes (dominating, locating, identifying, ...) in graphs and their applications.
    • Extremal combinatorics: the typical question in this field is "what global condition do we need to impose in some graph in order to make sure that some nice structure appears locally?" We will introduce a powerful tool called "the probabilistic method", an show how it can be applied to solve problems in this important area of research.
    Lire plus

    Heures d'enseignement

    • CMCM18h

    Période

    Semestre 9