Prof. Dr. Neil Olver (London School of Economics and Political Science, London, UK)
Thin trees for laminar families abstract
Abstract:
In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Using iterative relaxation, combined with a simple reduction technique, we show that the thin tree conjecture is true whenever the specified cuts form a laminar family.Joint work with Nathan Klein.
10:00 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 19.2