Return to Colloquia & Seminar listing
Minimal Spanning Trees - an overview
Student-Run Research Seminar| Speaker: | Matt Hubbard, UC Davis |
| Location: | 693 Kerr |
| Start time: | Wed, Jan 22 2003, 12:10PM |
The history of the minimal spanning tree (MST) problem will be discussed, including the "original" major application and the two famous solutions, Kruskal's and Prim's algorithms. The talk will also cover two well-known O(nlogn) sorting algorithms, QuickSort and HeapSort, an easily explained but difficult to solve sub-problem, the Manhattan Steiner MST, and a method for determining the number of MSTs in a weighted graph, based on ideas borrowed from Kruskal and Kirchhoff.