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

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

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

Answer:

According to the definition: "The pertinent subtree of T with respect to S, denoted PERTINENT(T, S), is the subtree of minimum height whose frontier contains all of S."

Therefore, if S= {H,F}, PERTINENT(T,S) is

pertinent subtree

since it is impossible to eliminate any node without eliminating an element from S, this is the minimum sub-tree.

For the prunned subtree, the definition is: "The pruned pertinent subtree of T with respect to S is the smallest connected subgraph (not necessarily a proper PQ-tree!) which contains all of the pertinent leaves."

For S={H, F}, PRUNNED(T,S) is the following:

prunned subtree

as there is no way of eliminating anything without disconnecting the tree or talking off an element of S, the tree above is the pruned pertinent subtree.


MO640 Home

© 2015 Joao Meidanis