# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree Using MLS  
The algorithms MCS, LexBFS, LexDFS and, more generally, the algorithm \(\mathcal{L}\)-MLS for any labeling structure \(\mathcal{L}\) for which the order on labels is total compute a PMO of a connected chordal graph [12]. Note that the definition of a labeling structure given in [12] is less general than the definition given in this paper, but the proof of this result still holds here. We define the algorithm moplex-MLS (Algorithm 5), which computes a PMO of a chordal graph, whether the order on labels is total or not, by adding, in the case where the ordering fails to be total, a tie-breaking rule for choosing a vertex with a maximal label. ```
input : a connected chordal graph \(H\) and a labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\) output : a PMO \(\alpha=(x_{1},\ldots,x_{n})\) of \(H\) \(V^{\prime}\leftarrow\mathcal{O}\); initialize all labels as \(l_{0}\); prev-max-label \(\gets\)\(l_{0}\); for\(i=n\)down to \(1\)do  Choose a vertex \(x\) in \(V\setminus V^{\prime}\) whose label is maximal,  and if possible strictly greater than prev-max-label; \(x_{i}\gets x\); foreach\(y\) in \(N_{H}(x)\setminus V^{\prime}\)do \(label(y)\gets Inc(label(y),i)\);  end foreach\(V^{\prime}\gets V^{\prime}\cup\{x\}\); prev-max-label \(\leftarrow\)\(label(x)\);  end foreach\(V^{\prime}\gets V^{\prime}\cup\{x\}\); prev-max-label \(\leftarrow\)\(label(x)\);  end foreach\(V^{\prime}\)
```  
**Algorithm 5**mplex-MLS. Theorem 3: _The algorithm moplex-MLS computes a PMO of a connected chordal graph._  
To prove Theorem 3, we will use the following Lemma. In an execution of moplex-MLS, for each \(i\) in \([1,n-1]\) and each \(y\) in \(V\) such that \(\alpha^{-1}(y)\leq i\), at the beginning of iteration \(i\),  
1. If \(N_{H}^{\alpha+}[x_{i+1}]\subseteq N_{H}^{\alpha,i}(y)\), then prev-max-label \(\prec\)\(label(y)\). 2. If prev-max-label \(\prec\)\(label(y)\), then \(\{x_{i+1}\}\subseteq N_{H}^{\alpha,i}(y)\subseteq N_{H}^{\alpha+}[x_{i+1}]\). Proof. : (a) If \(N_{H}^{\alpha+}[x_{i+1}]\subseteq N_{H}^{\alpha,i}(y)\), then \(N_{H}^{\alpha,i}(x_{i+1})\subset N_{H}^{\alpha,i}(y)\), so by Lemma 1, _prev-max-label \(=\) label\((x_{i+1})\prec\) label\((y)\)_. (b) We suppose that _prev-max-label \(\prec\) label\((y)\)_. As the label of \(x_{i+1}\) is maximal at the beginning of iteration \(i+1\), _label\((y)\)_ has been increased during iteration \(i+1\), so \(y\) is a neighbor of \(x_{i+1}\) in \(H\). As \(\alpha\) is an MLS ordering of \(H\), it is a PEO of \(H\), so \(N_{H}^{\alpha+}(y)\) is a clique containing \(x_{i+1}\), and therefore, \(N_{H}^{\alpha,i}(y)\subseteq N_{H}^{\alpha+}[x_{i+1}]\). Proof. : (of Theorem 3) Let \(\alpha=(x_{1},\ldots,x_{n})\) be the ordering computed by an execution of moplex-MLS on input \(H\) and \(\mathcal{L}\). Let us show that it is a PMO of \(H\). By Characterization 3, it is sufficient to show that \(\alpha\) is a MCComp PEO of \(H\). As \(\alpha\) is an MLS ordering of \(H\), it is a PEO of \(H\). Let \(i\in[1,n-1]\)We suppose that \(N_{H}^{\alpha+}[x_{i+1}]\) is not a maximal clique of \(H\). Let us show that it is equal to \(N_{H}^{\alpha+}(x_{i})\). As \(N_{H}^{\alpha+}[x_{i+1}]\) is not a maximal clique of \(H\), there is a vertex \(y\), such that \(\alpha^{-1}(y)\leq i\) and \(N_{H}^{\alpha+}[x_{i+1}]\subseteq N_{H}^{\alpha+j}(y)\), and therefore, by Lemma 3 (a), _prev-max-label_\(\prec\)_label_\((y)\) at the beginning of iteration \(i\) in this execution. It follows by the condition on the choice of \(x\) that _prev-max-label_\(\prec\)_label_\((x_{i})\), and therefore, by Lemma 3 (b), \(N_{H}^{\alpha+}(x_{i})\subseteq N_{H}^{\alpha+}[x_{i+1}]\). It is impossible that \(N_{H}^{\alpha+}(x_{i})\subset N_{H}^{\alpha+}[x_{i+1}]\) since in that case \(N_{H}^{\alpha+j}(x_{i})\subset N_{H}^{\alpha+j}(y)\), so by Lemma 1 at the beginning of iteration \(i\), _label_\((x_{i})\prec\)_label_\((y)\) and \(x_{i}\) would not be a vertex with maximal label. Hence, \(N_{H}^{\alpha+}(x_{i})=N_{H}^{\alpha+}[x_{i+1}]\).