MO640 - Exercises - PQ-trees, Booth and Lueker 1976

Exercises marked with (*) require further reading/search beyond the suggested texts.

1. Find a collection of sets S1, S2, ... Sk such that reducing an universal tree with respect to S1, then reducing the resulting tree with respect to S2, and so on will produce the PQ-tree in Figure 3 of Booth and Lueker's 1976 paper (or an equivalent tree).

   To help you with this exercise, you may want to use an online PQ-tree implementation such as:

   http://www.jharris.ca/portfolio/code/pqtree/PQTree.html

   There is also a generalization of this code for PQR trees:

   http://www.ic.unicamp.br/~meidanis/PUB/IC/2006-Dilly/PQRTree/

2. Find the root of the pertinent subtree and the set PRUNNED(T,S) for T = the tree in Figure 3 of Booth and Lueker's 1976 paper and S = {H, F}.

3. Reduce the tree in Figure 3 of Booth and Lueker's 1976 paper with respect to S = {E, K}. Here also the online implementation above can help you.

4. Reduce the tree in Figure 3 of Booth and Lueker's 1976 paper with respect to S = {C, F}. Here also the online implementation above can help you.

MO640 Home

© 2015 Joao Meidanis