Theory Seminar

Friday, October 14, 2016 - 2:30pm to 3:30pm

Location:

Traffic21 Classroom 6501 Gates & Hillman Centers

Speaker:

YIANNIS KOUTIS, Associate Professor http://ccom.uprrp.edu/~ikoutis/

Event Website:

http://theory.cs.cmu.edu/seminars/

For More Information, Contact:

nlc@cs.cmu.edu

We present fully dynamic algorithms for graph sparsification problems. The algorithms allow both edge insertions and edge deletions. For cut sparsification, the algorithm takes poly-logarithmic time for each update. For spectral sparsification, the algorithm takes poly-logarithmic time on average. We also discuss an application of these sparsification algorithms in a fully dynamic algorithm for maintaining an approximate minimum cut in an unweighted, undirected, bipartite graph. Joint work with I. Abraham, D. Durfee, S. Krinninger, R. Peng Faculty Host: Gary Miller

Keywords:

Seminar Series