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
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:
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.
© 2015 Joao Meidanis