Sign Up

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