Sequential and Parallel Algorithms for Some Problems on Trees

Add to your list(s) Download to your calendar using vCal

• Professor Raymond Greenlaw, Armstrong Atlantic State University, Georgia
• Friday 28 March 2008, 12:00-13:00
• Churchill College Møller Centre.

If you have a question about this talk, please contact Peter Robinson.

A node (edge) ranking of a tree is a labeling of the nodes (respectively, edges) using natural numbers such that on the path between any two nodes (respectively, edges) with the same label there is an intermediate node (respectively, edge) with a higher label. A node (edge) ranking is optimal if the highest label used is as small as possible.

These problems have applications in scheduling the manufacture of complex multi-part products. 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. We’ll discuss algorithms for these problems from both sequential and parallel perspectives.

This talk is part of the Alfaisal University Engineering Seminars series.

This talk is included in these lists:

• Alfaisal University Engineering Seminars
• Churchill College Møller Centre

Note that ex-directory lists are not shown.