Dynamic trees and algorithms

(i) Min_wt_edge(u,v): report the least weight edge on the path
between u and v.
(ii)Min_wt_vertex(u): report the weight of the least weight vertex
in the tree to which vertex u belongs.
(iii)Radius(u): report the radius of the tree to which
vertex u belongs.

There are data structures which can answer each of the above queries in just O(log n) time. These data structures are called dynamic trees. In this talk we shall discuss two such dynamic trees, namely Link/cut trees and Euler tour trees. These dynamic trees, in addition to being of independent interest, have played vital roles in the design of efficient dynamic algorithms for various graph problems.

IMPORTANT NOTE:
This talk will serve as a warm-up for a mini lecture series on dynamic graph algorithms. However, the talk will be totally self contained. So in case you are interested in dynamic trees only, you might find this talk worth attending. The only prerequisite for this talk (and the lecture series) is a basic knowledge of data structures and algorithms.