# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree from a PMO
Let us show that it is preserved at iteration \(i\), with \(1\leq i\leq n\). Let (a1) (resp. (b1),..., (e1)) denote Item (a) (resp. (b),..., (e)) at the beginning of iteration \(i\) (which is supposed to be true), and let \(s\) be the value of this variable at the beginning of iteration \(i\). We prove that (a), (b) and (c) are preserved as in the proof of Invariant 1, except that we have moreover to show that if \(K_{s}\
eq S\), then \(K_{p}\
eq S\). It is evident if \(p=s\); otherwise, it follows from the fact that \(K_{p}\) is a maximal clique of \(H\) by (d1), whereas \(S\) is not, since it is a strict subset of the clique \(S\cup\{x\}\). Hence, (a), (b) and (c) are preserved. Let us show that (d) is preserved. We only have to check that in case \(s\) is incremented (to \(s+1\)), \(K_{s}\) is a maximal clique of \(H\). As \(s\) is incremented at iteration \(i\)\(K_{s}\
eq S\), so \(i<n\), and therefore, by (e1), \(K_{s}=N_{H}^{a+}[x_{i+1}]\). As \(K_{s}\
eq S\) with \(S=N_{H}^{a+}(x_{i})\) and \(\alpha\) is a MCComp PEO of \(H\), it follows that \(K_{s}\) is a maximal clique of \(H\). Thus, (d) is preserved, and (e) obviously holds at the end of iteration \(i\). **Characterization 3**: _An ordering \(\alpha\) of a connected chordal graph \(H\) is a MCComp PEO of \(H\) if and only if it is a PMO of \(H\)._  
Proof: We prove this by induction on \(n=|V|\). The result trivially holds if \(n=1\). We suppose that it holds if \(|V|<n\). Let us show that it holds if \(|V|=n\). Let \(\alpha=(x_{1},\ldots,x_{n})\) be an ordering of \(H\), and let \(H^{\prime}=H(V\setminus\{x_{1}\})\). \(\Rightarrow\): We suppose that \(\alpha\) is a MCComp PEO of \(H\). Let us show that it is a PMO of \(H\). \((x_{2},\ldots,x_{n})\) is a MCComp PEO of \(H^{\prime}\), so by the induction hypothesis, it is a PMO of \(H^{\prime}\) compatible with a perfect moplex partition of \(H^{\prime}\), say \((X_{1},\ldots,X_{k})\). If \(N_{H}^{a+}(x_{1})=N_{H}^{a+}[x_{2}]\), then \((\{x_{1}\}\cup X_{1},\ldots,X_{k})\) is a perfect moplex partition of \(H\). Otherwise, in an execution of the algorithm MCComp-CliqueTree on \(H\) and \(\alpha\), \(K_{s}\
eq S\) at Iteration 1 since \(S=N_{H}^{a+}(x_{1})\) and \(K_{s}=N_{H}^{a+}[x_{2}]\) by Invariant 2 (e), so \(S\) is a minimal separator of \(H\), which makes \(\{x_{1}\}\) a moplex of \(H\) and \((\{x_{1}\},X_{1},\ldots,X_{k})\) a perfect moplex partition of \(H\). Hence, \(\alpha\) is a PMO of \(H\). \(\Leftarrow\): We suppose that \(\alpha\) is a PMO of \(H\) compatible with perfect moplex partition \((X_{1},\ldots,X_{k})\). Let us show that it is a MCComp PEO of \(H\). As it is a PMO of \(H\), it is a PEO of \(H\). \((x_{2},\ldots,x_{n})\) is a PMO of \(H^{\prime}\) (compatible with perfect moplex partition \((X_{2},\ldots,X_{k})\) if \(X_{1}=\{x_{1}\}\) and \((X_{1}\setminus\{x_{1}\},\ldots,X_{k})\) otherwise), so by the induction hypothesis, it is a MCComp PEO of \(H^{\prime}\). Hence, for each \(i\) from two to \(n-1\), \(N_{H}^{a+}[x_{i+1}]\) is a maximal clique of \(H^{\prime}\) or equal to \(N_{H}^{a+}(x_{i})\). It is sufficient to show that for each \(i\) from two to \(n-1\), if \(N_{H}^{a+}[x_{i+1}]\) is a maximal clique of \(H^{\prime}\), then it is a maximal clique of \(H\) and that \(N_{H}^{a+}[x_{2}]\) is a maximal clique of \(HIn that case, \(N_{H}^{\alpha+}(x_{1})=N_{H}^{\alpha+}[x_{2}]\). By Lemma 2, each maximal clique of \(H^{\prime}\) different from \(N_{H}(x_{1})\) is a maximal clique of \(H\). It follows that for each \(i\) from two to \(n-1\), if \(N_{H}^{\alpha+}[x_{i+1}]\) is a maximal clique of \(H^{\prime}\), then it is a maximal clique of \(H\), since it does not contain \(x_{2}\), whereas \(N_{H}(x_{1})\) contains \(x_{2}\). The algorithm MCComp-CliqueTree computes a clique tree and the set of minimal separators of a connected chordal graph \(H\) from a PMO of \(H\) in linear time.