Abstract

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].

Video Recording