# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree Using MLS
```
input : a connected chordal graph \(H\) and a DCL labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\) output : a PMO \(\alpha=(x_{1},\ldots,x_{n})\), a clique tree \(T\) and the set \(Sep\) of minimal separators of \(H\) InitCT;  Initialize all labels as \(l_{0}\); prev-max-label \(\gets\)\(l_{0}\); for\(i=n\)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\); \(S\gets N_{H}(x)\cap V^{\prime}\); // \(S=N_{H}^{\alpha+}(x)\) ifprev-max-label \(\
ot<\) label\((x)\) and \(i<n\)then  StartClique;  end if IncreaseClique; foreach\(y\) in \(N_{H}(x)\setminus V^{\prime}\)do \(label(y)\gets Inc(label(y),i)\);  end if \(V^{\prime}\gets V^{\prime}\cup\{x\}\); prev-max-label \(\leftarrow\) label\((x)\);  end for DefineCT;
```  
**Algorithm 7**DCL-MLS-CliqueTree. Theorem 4: _The algorithm DCL-MLS-CliqueTree is correct and would be incorrect with any non-DCL input labeling structure. Moreover, if the input labeling structure is \(\mathcal{L}_{X}\) with \(X\in\{MCS,LexBFS\}\), then the algorithm runs in linear time._  
Proof: We suppose that \(\mathcal{L}\) is DCL. It is sufficient to show that at each iteration \(i\) in \([1,n-1]\), \(K_{s}=S\Leftrightarrow\textit{prev-max-label}\prec label(x)\), i.e., by Invariant 2 (e), \(N_{H}^{\alpha+}[x_{i+1}]=N_{H}^{\alpha,l}(x_{i})\Leftrightarrow\textit{prev- max-label}\prec label(x)\). The implication from left to right immediately follows from Lemma 3 (a). Let us show the reverse implication. We suppose that \(\textit{prev-max-label}\prec label(x_{i})\). By Lemma 3 (b), \(\{x_{i+1}\}\subseteq N_{H}^{\alpha,i}(x_{i})\subseteq N_{H}^{\alpha+}[x_{i+1}]\). Let \(I=\alpha^{-1}(N_{H}^{\alpha,i+1}(x_{i}))\), and let \(I^{\prime}=\alpha^{-1}(N_{H}^{\alpha+}(x_{i+1}))\). \(I\subseteq I^{\prime}\subseteq[i+2,n]\) and \(lab_{\mathcal{L}}(I^{\prime})=\textit{prev-max-label}\prec label(x_{i})= lab_{\mathcal{L}}(I\cup\{i+1\})\), so \(I=I^{\prime}\), since \(\mathcal{L}\) is DCL. It follows that \(N_{H}^{\alpha+}[x_{i+1}]=N_{H}^{\alpha,i}(x_{i})\). We suppose now that \(\mathcal{L}\) is not DCL. Then, there are some integers \(i\) and \(n\) with \(1\leq i<n\) and some subsets \(I\) and \(I^{\prime}\) of \([i+2,n]\) such that \(I\subset I^{\prime}\) and \(lab_{\mathcal{L}}(I^{\prime})\prec lab_{\mathcal{L}}(I\cup\{i+1\})\). Let \(H=(V,E)\) and \(\alpha\) be defined by: \(V=\{1,\ldots,n\}\), \(\alpha=(1,\ldots,n)\), \(\{i+2,\ldots,n\}\) is a clique of \(H\), \(N_{H}^{\alpha+}(i+1)=I^{\prime}\) and \(\forall j\in[1,i]\)\(N_{H}^{\alpha+}(j)=I\cup\{i+1\}\). \(H\) is connected and chordal and by IC \(\alpha\) can be computed by an execution of the algorithm DCL-MLS-CliqueTree. At iteration \(i\) of such an execution, \(K_{s}\
eq S\), but \(\mathit{prev-max-label}=\mathit{lab}_{\mathcal{L}}(I^{\prime})\prec\mathit{lab}_{ \mathcal{L}}(I\cup\{i+1\})=\mathit{label}(x)\), so the execution increases current clique \(K_{s}\) instead of starting a new one. We suppose that the input labeling structure is \(\mathcal{L}_{X}\) with \(X\in\{\mathit{MCS},\mathit{LexBFS}\}\). As the order on labels is total, it is sufficient to choose a vertex \(x\) with the maximal label at each iteration. As \(\mathcal{L}_{X}\)-MLS runs in linear time, it is sufficient to check that condition \(\mathit{prev-max-label}\
ot\prec\mathit{label}(x)\) can be evaluated in \(O(|N_{H}(x)|)\) time. It is obviously the case if \(X=\mathit{MCS}\). It is also the case if \(X=\mathit{LexBFS}\) since \(\mathit{label}(x)\) is of a length of at most \(|N_{H}(x)|\). For \(X=\mathit{MCS}\) (resp. \(\mathit{LexBFS}\)), as \(\mathcal{L}_{X}\) is DCL with totally ordered labels, the algorithm DCL-\(\mathcal{L}_{X}\)-MLS-CliqueTree can be simplified by choosing an arbitrary vertex with the maximal label at each iteration, yielding the algorithms from [4] (resp. [13]).