Talks
Fall 2015

Some Emergency Barriers to Worst-Case Dynamic MST

Wednesday, December 2nd, 2015, 2:45 pm3:30 pm

Add to Calendar

Breaking the the worst case update time of Frederickson [STOC 1983] and Eppstein~et~al. [FOCS 1992] for the dynamic minimum spanning tree (dynamic MST) problem has long been an elusive question. In this talk I will discuss some of the barriers to this goal in the emergency planning setting as formulated by Patrascu and Thorup [FOCS 2007].