University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Thin spanning trees and their algorithmic applications

Thin spanning trees and their algorithmic applications

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact info@newton.ac.uk.

SNAW01 - Graph limits and statistics

Motivated by Jaeger's modular orientation conjecture, Goddyn asked the following question: 

A spanning tree of a graph G is called epsilon-thin if it contains at most an epsilon fraction of the edges of each cut in that graph. Is there a function f:(0,1)→ ℤ such that every f(epsilon)-edge-connected graph has an epsilon-thin spanning tree?
 
I will talk about our journey in search of such thin trees, their applications concerning traveling salesman problems, and unexpected connections to graph sparsification and the Kadison-Singer problem.

Bio: saberi/bio.txt" target="_blank" rel="nofollow">http://stanford.edu/saberi/bio.txt

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity