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

Bookmarks Report an error
Multi angle
Authors : Lokshtanov, Daniel (Author of the conference)
CIRM (Publisher )

Loading the player...

Abstract : 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.

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

    Information on the Video

    Film maker : Hennenfent, Guillaume
    Language : English
    Available date : 04/02/15
    Conference Date : 22/01/15
    Subseries : Research talks
    arXiv category : Computer Science ; Combinatorics
    Mathematical Area(s) : Combinatorics ; Computer Science
    Format : MP4 (.mp4) - HD
    Video Time : 00:44:45
    Targeted Audience : Researchers
    Download : https://videos.cirm-math.fr/2015-01-22_Lokshtanov.mp4

Information on the Event

Event Title : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphes
Event Organizers : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, Paul
Dates : 19/01/15 - 23/01/15
Event Year : 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

Bibliography



Bookmarks Report an error