Campus Event Calendar

Event Entry

What and Who

Dynamic trees and algorithms

Surender Baswana
IIT Kanpur
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
AG Audience

Date, Time and Location

Tuesday, 22 May 2012
45 Minutes
E1 4


Consider a collection of unrooted trees on n vertices where each edge (or vertex) may have a weight which is a real number. The trees as well as the weights (of edges/vertices) keep changing in an online fashion. For example, we may join two trees by an edge or we may delete an edge and thus split the tree into two trees. Likewise, we may change the weight of edge(or vertex). Now think of some queries which we would like to answer efficiently in such a dynamic scenario. A few examples of the types of queries are:

(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.

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.


Megha Khosla
--email hidden
passcode not visible
logged in users only

Uwe Brahm, 05/21/2012 16:18
Megha Khosla, 05/09/2012 10:40
Megha Khosla, 05/09/2012 10:39 -- Created document.