[Colloquium] [TTIC Talks] Talks at TTIC: Dan Larkin, Princeton

[Shi Li]

Dan will be around TTIC after the talk until 5:00pm.  Please let me know 
if you would like to meet with him.

On 10/29/2014 9:09 AM, Dawn Ellis wrote:
> 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 <mailto:shili at ttic.edu>
>
> -- 
> /Dawn Ellis/
> Administrative Coordinator,
> Bookkeeper
> 773-834-1757
> dellis at ttic.edu <mailto: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/fef755e7/attachment.htm