PQ-Tree

Which of the affirmatives bellow are true about the Booth and Lueker's algorithm to build a PQ-tree:

I - The algorithm has two steps, one to identify the nodes that must be processed and another to apply the reductions.
II - Every son of a Q node has pointers to his fathers
III - The linear complexity is confirmed by doing an amortized analysis

A. I and II
B. I and III
C. II
D. III
E. None of the above

Author: Maria Angélica Lopes de Souza

Translated by: Rafael Soares Padilha