m
• E

F Nous contacter

0

Multi angle

H 1 Tree decompositions and graph algorithms

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

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 graphesOrganisateurs de la rencontre : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, PaulDates : 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

Bibliographie

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

0
Z