Authors : Lokshtanov, Daniel (Author of the conference)
CIRM (Publisher )
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
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
|
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
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
- 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