F Nous contacter

Multi angle

H 1 Tree decompositions and graph algorithms

Auteurs : Lokshtanov, Daniel (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions.

    Codes MSC :
    05C35 - Extremal problems (graph theory)
    05C85 - Graph algorithms
    68Q25 - Analysis of algorithms and problem complexity

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 04/02/15
      Date de captation : 22/01/15
      Collection : Research talks ; Combinatorics ; Computer Science
      Format : quicktime ; audio/x-aac
      Durée : 00:44:45
      Domaine : Combinatorics ; Computer Science
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2015-01-22_Lokshtanov.mp4

    Informations sur la rencontre

    Nom de la rencontre : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphes
    Organisateurs de la rencontre : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, Paul
    Dates : 19/01/15 - 23/01/15
    Année de la rencontre : 2015

    Citation Data

    DOI : 10.24350/CIRM.V.18673103
    Cite this video as: Lokshtanov, Daniel (2015). Tree decompositions and graph algorithms. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18673103
    URI : http://dx.doi.org/10.24350/CIRM.V.18673103


    1. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2014). On cutwidth parameterized by vertex cover. Algorithmica, 68(4), 940-953 - http://dx.doi.org/10.1007/s00453-012-9707-6

Ressources Electroniques (Depuis le CIRM)

Books & Print journals

Recherche avancée