# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree from a PMO  
According to Invariant 1, in an execution of the algorithm CliqueTree, the cliques \(K_{1},\ldots,K_{s}\) are the maximal cliques of \(H(V^{\prime})\) and, therefore, cliques of \(H\) that are not necessarily maximal in \(H\). Some PEOs build the maximal cliques of \(H\) one after another: at each time in an execution of the algorithm, each clique \(K_{j}\) different from \(K_{s}\) is a maximal clique of \(H\), and a vertex is added to \(K_{s}\) at each iteration of the **for** loop until \(K_{s}\) is a maximal clique of \(H\); and \(s\) is incremented to start a new maximal clique of \(H\). If \(\alpha=(x_{1},\ldots,x_{n})\) is such a PEO, at the beginning of iteration \(i<n\), the current clique \(K_{s}\) is equal to \(N_{H}^{\pm+}[x_{i+1}]\), and if \(K_{s}\) is not a maximal clique of \(H\), then \(K_{s}=S=N_{H}^{\pm+}(x_{i})\) and \(x_{i}\) is added to \(K_{s}\) at iteration \(i\). A MCComp (Maximal Clique Completing) PEO of a connected chordal graph \(H\) is a PEO \(\alpha=(x_{1},\ldots,x_{n})\) of \(H\) such that for each \(i\in[1,n-1]\), \(N_{H}^{\pm+}[x_{i+1}]\) is a maximal clique of \(H\) or equal to \(N_{H}^{\pm+}(x_{i})\). **Example 1**. : _Let \(H\) be the graph shown in Figure 1, whose maximal cliques are \(K=\{a,b,f\}\), \(K^{\prime}=\{c,d,e\}\) and \(\{e,f\}\), and let \(\alpha=(a,b,c,d,e,f)\). An execution of CliqueTree on \(H\) and a successively completes the maximal cliques \(\{e,f\}\), \(K^{\prime}\) and \(K\), and we easily check that \(\alpha\) is a MCComp PEO of \(H\). Now, let \(\beta=(a,c,d,b,e,f)\). An execution of CliqueTree on \(H\) and \(\beta\) successively completes \(\{e,f\}\), starts K, starts and completes \(K^{\prime}\) and, finally, completes \(K\). \(\beta\) is not a MCComp PEO of \(H\) since for \(i=3\), \(N_{H}^{\beta+}[x_{i+1}]\) is neither a maximal clique of \(H\), nor equal to \(N_{H}^{\beta+}(x_{i})\) (\(N_{H}^{\beta+}[x_{i+1}]=N_{H}^{\beta+}[b]=\{b,f\}\) and \(N_{H}^{\beta+}(x_{i})=N_{H}^{\beta+}(d)=\{e\}\))._  
Using a MCComp PEO instead of an arbitrary PEO, the algorithm CliqueTree can be simplified into the algorithm MCComp-CliqueTree (Algorithm 4) containing the blocks **InitCT**, **StartClique**, **IncreClique** and **DefineCT**, which will be used in further algorithms in this paper. **InitCT** // _Initialize the Clique Tree_  
\(V^{\prime}\leftarrow\emptyset;s\gets 1;K_{1}\leftarrow\emptyset;E \leftarrow\emptyset;Sep\leftarrow\emptyset;\)__  
**StartClique** // _Start a new Clique_  
\(s\gets s+1;K_{s}\gets S;\)__  
\(k\gets min\{j,\alpha(j)\in S\};\)__\(p\gets clique(\alpha(k))\)_;_  
\(E\gets E\cup\{(p,s)\};Sep\gets Sep\cup\{S\};\)__  
**IncreaseClique** // _Increase the current Clique_  
\(K_{s}\gets K_{s}\cup\{x\};\)__\(clique(x)\gets s;\)__  
**DefineCT** // _Define the Clique Tree_  
\(T\leftarrow(\{K_{1},\ldots,K_{s}\},\{K_{p}K_{q},\ (p,q)\in E\})\)_;_  
```
input : a connected chordal graph \(H\) and a MCComp PEO \(\alpha=(x_{1},\ldots,x_{n})\) of \(H\) output : a clique tree \(T\) and the set \(Sep\) of minimal separators of \(H\) InitCT; for\(i=n\)down to\(1\)do \(x\gets x_{i};S\gets N_{H}(x)\cap V^{\prime};//\ S=N_{H}^{\alpha+}(x)\) if\(K_{s}\
eq S\)then StartClique; end if IncreaseClique; \(V^{\prime}\gets V^{\prime}\cup\{x\};\) end for DefineCT;
```  
**Algorithm 4**MCComp-CliqueTree. Figure 1: A chordal graph \(H\). Theorem 2: _The algorithm MCComp-CliqueTree computes a clique tree and the set of minimal separators of a connected chordal graph \(H\) from a MCComp PEO of \(H\) in linear time._  
Proof: The proof of complexity is similar to that of Theorem 1, and the correctness of the algorithm follows from Invariant 2. **Invariant 2**: _The following proposition is an invariant of the **for** loop of the algorithm MCComp-CliqueTree:_  
* _(a) (b) (c) (as in Invariant 1)_
* _(d)_ \(\forall j\in[1,s-1]\)__\(K_{j}\) _is a maximal clique of_ \(H\)_,_
* _(e)_ \(K_{s}=N_{H}^{a+}[x_{i}]\)_._  
Proof: The proposition clearly holds at the initialization step (except for (e), which is undefined).