Return to Colloquia & Seminar listing
Minimal Spanning Trees - an overview
Student-Run Research| Speaker: | Matt Hubbard, UC Davis |
| Location: | 693 Kerr |
| Start time: | Wed, Jan 22 2003, 12:10PM |
Description
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.