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

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

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.

Answer:

Figure 3 of Booth and Lueker's 1976 paper is:

original tree and reduced tree

Using the online PQ-tree implementation available at

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

the reduction goes through the following steps: Step 1: "C" becomes full

original tree and reduced tree

Step 2: "F" becomes full

original tree and reduced tree

Step 3: The parent of "E" and "F" becomes a partial Q-Node, and "E" and "F" are reversed

original tree and reduced tree

Step 4: This step does not correspond to a pattern, thus the final reduction is a null tree.