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).

Answer:

To produce a tree equivalent to the PQ-Tree of Figure 3 in the Booth and Lueker's 1976 paper, we can follow the steps below:

1 - reduce {G,H,I}
2 - reduce {I,J,K}
3 - reduce {D,E,F}
4 - reduce {E,F,G,H,I,J,K}

MO640 Home

© 2015 Joao Meidanis