About this Event
McKelvey Hall, McKelvey 1020
Zihao Deng
PhD Candidate
Computer Science & Engineering
Washington University in St. Louis
Minimum spanning trees are very helpful in many network design related applications and algorithms. They are often used in water networks, electrical grids, and computer networks. In this presentation I will discuss the formulation of the network design problem and two greedy algorithms for constructing minimum spanning trees to solve this problem, i.e., Kruskal’s algorithm and Prim’s algorithm. I will then explain the cut property, an important structural property of minimum spanning trees, and use it to prove the effectiveness of both these algorithms.
Talk Location: McKelvey 1020