En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Tree decompositions and graph algorithms

Sélection Signaler une erreur
Multi angle
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

    Réalisateur : Hennenfent, Guillaume
    Langue : Anglais
    Date de publication : 04/02/15
    Date de captation : 22/01/15
    Sous collection : Research talks
    arXiv category : Computer Science ; Combinatorics
    Domaine : Combinatorics ; Computer Science
    Format : MP4 (.mp4) - HD
    Durée : 00:44:45
    Audience : Researchers
    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

Données de citation

DOI : 10.24350/CIRM.V.18673103
Citer cette vidéo: 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

Bibliographie



Sélection Signaler une erreur