Talk: Minimum Spanning Trees: Verification and Randomized Construction - Torben Hagerup
Institut für Informatik, Universität Augsburg
Friday 8. April, 14:00 s.t.
Forschungsgruppe Scientific Computing
Seminarraum C316, Nordbergstraße 15/3C
The talk sketches a randomized algorithm due to Karger, Klein and Tarjan for computing minimum spanning trees in expected linear time and then
focuses on a key subproblem faced by that algorithm, the linear-time verification of minimum spanning trees.
More precisely, a new linear-time algorithm due to the speaker is presented for the tree-path-maxima problem of, given a tree T with real edge weights and a list of pairs of distinct nodes in T , computing for each pair (u, v) on the list a maximum-weight edge on the path in T between u and v. Linear-time algorithms for the tree-path-maxima problem were known previously, but the new algorithm may be considered significantly simpler than the earlier solutions. A linear-time algorithm for the tree-path-maxima problem can be used as a component in the Karger-Klein-Tarjan algorithm and implies a linear-time algorithm for the MST-verification problem of, given a spanning tree T of an undirected graph G with real edge weights, determining whether T is a minimum-weight spanning tree of G.