University of Cambridge > Talks.cam > Alfaisal University Engineering Seminars > Sequential and Parallel Algorithms for Some Problems on Trees

Sequential and Parallel Algorithms for Some Problems on Trees

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity