# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree Using MLS
If \(\mathcal{L}\) is a labeling structure with a total order on labels, condition \"if possible strictly greater than _prev-max-label_\" is useless, so the algorithm complex-\(\mathcal{L}\)-MLS is actually identical to \(\mathcal{L}\)-MLS. We thus provide an alternate proof for the result from [12] that if the order on labels is total, then each \(\mathcal{L}\)-MLS ordering of a chordal graph is a PMO of this graph, with a more general definition of a labeling structure and an alternative (simpler) proof. Combining algorithms MCComp-CliqueTree and complex-MLS, we define the algorithm MLS-CliqueTree (Algorithm 6) computing both a PMO and a clique tree of a chordal graph. ```
input : a connected chordal graph \(H\) and a labeling structure \(\mathcal{L}=(L,\preceq,l_{0},\mathit{Inc})\) output : a PMO \(\alpha=(x_{1},\ldots,x_{n})\), a clique tree \(T\) and the set \(\mathit{Sep}\) of minimal separators of \(H\) InitCT;  Initialize all labels as \(l_{0}\); prev-max-label \(\leftarrow\)\(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 \(\mathit{prev-max-label}\); \(x_{i}\gets x\); \(S\leftarrow N_{H}(x)\cap V^{\prime}\); // \(S=N_{H}^{\alpha+}(x)\) if\(K_{s}\
eq S\)then StartClique;  end if IncreaseClique; foreach\(y\) in \(N_{H}(x)\setminus V^{\prime}\)do \(\mathit{label}(y)\leftarrow\mathit{Inc}(\mathit{label}(y),i)\);  end if \(V^{\prime}\gets V^{\prime}\cup\{x\}\); prev-max-label \(\leftarrow\)label\((x)\);  end for DefineCT;
```  
**Algorithm 6**MLS-CliqueTree. The correctness of the algorithm MLS-CliqueTree immediately follows from Corollary 1 and Theorem 3. **Example 2**. : _Consider an execution of the algorithm MLS-CliqueTree on the graph \(H\) shown in Figure 1 and labeling structure \(\mathcal{L}_{X}\) with \(X\in\{\mathit{MCS},\mathit{LexBFS},\mathit{LexDFS},\mathit{MNS}\}\) choosing vertices \(f\), then \(e\) first (and, therefore, completing the maximal clique \(\{e,f\}\) first). Then, the execution successively completes \(K\), then \(K^{\prime}\) if \(X=\mathit{LexBFS}\), \(K^{\prime}\), then \(K\) if \(X=\mathit{LexDFS}\), and either \(K\), then \(K^{\prime}\) or \(K^{\prime}\), then \(K\) otherwise. Removing condition \"if possible strictly greater than prev-max-label\" has no effect if \(X\
eq\mathit{MNS}\), but if \(X=\mathit{MNS}\), it would allow the execution to choose alternatively a vertex of \(K\) and a vertex of \(K^{\prime}\), as the labels of the vertices of \(K\) are incomparable to the labels of the vertices of \(K^{\prime}\)._  
The algorithm MLS-CliqueTree generalizes the algorithm extended-MCS from [4] and its extension to LexBFS from [13], except that in these algorithms, the condition \"\(K_{s}\
eq S\)\" is replaced by a direct condition on labels: \"\(\mathit{label}(x)\preceq\mathit{prev-max-label}\)\". We define a necessary and sufficient condition on a labeling structure \(\mathcal{L}\) for the replacement of \"\(K_{s}\
eq S\)\" by \"_prev-max-label_\(\
ot<\)_label_\((x)\)\" (which becomes \"\(label(x)\preceq\)_prev-max-label_\" if \(\preceq\) is a total order) to be possible. Definition 5: Let \(\mathcal{L}=(L,\preceq,l_{0},Inc)\) be a labeling structure. \(\mathcal{L}\) is DCL (Detect new Cliques with Labels) if for any integers \(i\) and \(n\) such that \(1\leq i<n\) and any subsets \(I\) and \(I^{\prime}\) of \([i+2,n]\), if \(I\subseteq I^{\prime}\) and \(lab_{\mathcal{L}}(I^{\prime})\prec lab_{\mathcal{L}}(I\cup\{i+1\})\), then \(I=I^{\prime}\). The labeling structures associated with MCS, LexBFS and MNS are clearly DCL, but \(\mathcal{L}_{LexDFS}\) is not since for any subsets \(I\) and \(I^{\prime}\) of \([i+2,n]\), \(lab_{\mathcal{L}}(I^{\prime})\prec lab_{\mathcal{L}}(I\cup\{i+1\})\) necessarily holds. Remark 1: _For each \(X\in\{MCS,LexBFS,MNS\}\), \(\mathcal{L}_{X}\) is a DCL labeling structure, but \(\mathcal{L}_{LexDFS}\) is not._  
On a DCL labeling structure, the algorithm DCL-MLS-CliqueTree (Algorithm 7) detects new cliques by a condition on abels.