Groupe

2023-2024

Vendredi 22 septembre à 14h - Théo Pierron
Spanning tree reconfiguration
Given n points in the plane, a spanning tree is a set of n-1 straight line edges connecting them while inducing a tree. We consider only those trees that are non-crossing, i.e. where no two edges are allowed to cross. Our goal is to transform a tree into another using as few operations as possible. Here, the operations consist in adding an edge and removing another so that the resulting graph remains a non-crossing spanning tree. While it is easy to show that there is a transformation between any two non-crossing spanning trees, beating the 2n naive upper bound stood up as an open problem for 25 years. In this talk, we will present the recent improvements on this topic.

This is based on joint works with Nicolas Bousquet, Valentin Gledel, Lucas De Meyer, Jonathan Narboni and Alexandra Wesolek.

Vendredi 15 septembre à 14h - Saeed Odak
An Optimal Algorithm for Product Structure in Planar Graphs
The Product Structure Theorem for planar graphs (Dujmovic et al. JACM, 67(4):22) states that any planar graph is contained in the strong product of a planar 3-tree, a path, and a 3-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous O(n log n) time algorithm (Morin. Algorithmica, 85(5):1544–1558).

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki