TuesdaY, ApriL 18, Volen 101, 2:00-3.00 pm
This talk covers Prufer codes, some fundamental parallel computing models and algorithms, and optimal parallel algorithms for computing Prufer codes. A Prufer code of a labeled free tree with n nodes is a sequence of length n-2 constructed by the following sequential process: for i ranging from 1 to n-2 insert the label of the neighbor of the smallest remaining leaf into the ith position of the sequence, and then delete the leaf. Prufer codes provide an alternative to the usual representation of trees. This is joint work with Rossella Petreschi of the University of Rome ``La Sapienza'' and Magnus Halldorsson of the University of Iceland.
Host: Jim Storer