[Colloquium] Talks at TTIC: Dan Larkin, Princeton

[Dawn Ellis]

When:     Thursday, October 30th at 2pm

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Dan Larkin, Princeton

Title:       Nested Set Union

Abstract:

We consider a version of the classic disjoint set union (union-find)
problem in which
there are two partitions of the elements, rather than just one, but
restricted such that
one partition is a refinement of the other. We call this the nested set
union problem.
This problem occurs in a new algorithm to find dominators in a flow graph.
One can
solve the problem by using two instances of a data structure for the
classical problem,
but it is natural to ask whether these instances can be combined. We show
that the
answer is yes: the nested problem can be solved by extending the classic
solution to
support two nested partitions, at the cost of at most a few bits of storage
per element
and a small constant overhead in running time. Our solution extends to
handle any
constant number of nested partitions.

Host:  Shi Li,  shili at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141029/298b965b/attachment.htm