Raimund Seidel

CS 789 THEORY SEMINAR [home]

Speaker:  Raimund Seidel 
Affiliation: Saarland University 
Date: Monday, May 5, 2003
Title: Top-Down Analysis of Union-Find

Abstract:

The union-find problem is one of the basic problems in algorithmics.

Its natural computational complexity is expressed in terms of

the extremely slowly growing, so-called "Inverse Ackermann" function.

I will present a way of analyzing the running times of union-find

algorithms that is based on a relatively simple top-down approach

and naturally leads to this "Inverse Ackermann" function (without

ever having to talk about the Ackermann function itself).