Revisit minimum spanning treeSpeaker: Fred
Title: Revisit minimum spanning tree
Date: 20 Sep 2018 5:30pm-7:00pm
Location: Northwest Building B150
Food: Thai food
Abstract: We revisit the the first (randomized) linear time algorithm for MST, due to Karger, Klein and Tarjan (J. ACM ‘95). I will present the whole algorithm and its analysis in 30 minutes. The problem of deterministic linear-time algorithm for MST is still open. Paradoxically, we do know an optimal algorithm (Pettie and Ramachandran, J. ACM ‘02), whose running time is unknown.