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 INI IT.
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 epsilonthin 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)edgeconnected graph has an epsilonthin 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 KadisonSinger 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.
This talk is included in these lists:
Note that exdirectory lists are not shown.
