# Computing a Clique Tree with the Algorithm Maximal Label Search
## 3 MLS and Clique Trees
### Clique Tree from a PEO  
The algorithm CliqueTree (Algorithm 3) from [PERSON] ([26], p. 258) is a slight variant of an algorithm originally given by [PERSON] [3] to compute a clique tree of a connected chordal graph from an arbitrary PEO of this graph. ```
input : a connected chordal graph \(H\) and a PEO \(\alpha=(x_{1},\ldots,x_{n})\) of \(H\) output : a clique tree \(T\) and the set \(\mathit{Sep}\) of minimal separators of \(H\) \(V^{\prime}\leftarrow\emptyset;s\gets 1\); \(K_{1}\leftarrow\emptyset\); \(E\leftarrow\emptyset\); \(\mathit{Sep}\leftarrow\emptyset\); 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\(i=n\)then \(p\gets 1\);  end if else \(k\gets min\{j,\alpha(j)\in S\}\); \(//\ S\
eq\emptyset\) because \(H\) is connected, \(\alpha\) is a PEO of \(H\) and \(i<n\)\(p\gets clique(\alpha(k))\);  end for if\(K_{p}=S\)then \(\mathit{clique}(x)\gets p\);  end if else \(s\gets s+1;K_{s}\gets S\); \(//\) start a new clique \(E\gets E\cup\{(p,s)\}\); \(\mathit{Sep}\leftarrow\mathit{Sep}\cup\{S\}\); \(//\ S=K_{p}\cap K_{s}\) \(\mathit{clique}(x)\gets s\);  end if \(K_{\mathit{clique}(x)}\gets K_{\mathit{clique}(x)}\cup\{x\}\); \(//\) increase clique \(V^{\prime}\gets V^{\prime}\cup\{x\}\);  end for \(T\leftarrow(\{K_{1},\ldots,K_{s}\},\{K_{p}K_{q},\ (p,q)\in E\})\);
```  
**Algorithm 3**CliqueTree. Theorem 1 ([3; 26]): _The algorithm CliqueTree computes a clique tree and the set of minimal separators of a connected chordal graph \(H\) from a PEO of \(H\) in linear time._Note that the algorithms from [3; 26] only compute a clique tree of the input graph. By Characterization 1, the algorithm CliqueTree correctly computes the set of minimal separators, and it does so in linear time using a search/insert structure for _Sep_, which allows checking for the presence of a set \(S\) and inserting it in \(O(|S|)\) time. The proofs given in [3; 26] implicitly use Invariant 1 below, which is explicitly stated and proven here, since it will be used later in this paper. To prove it, we will use the following lemma. Let \(H\) be a connected chordal graph; let \(x\) be a simplicial vertex of \(H\); let \(H^{\prime}=H(V\setminus\{x\})\); let \(T^{\prime}\) be a clique tree of \(H^{\prime}\); let \(K\) be a node of \(T^{\prime}\) containing \(N_{H}(x)\); let \(K^{\prime}=N_{H}[x]\); and let \(T\) be the tree obtained from \(T^{\prime}\) by replacing node \(K\) by \(K^{\prime}\) (with the same neighbors in \(T\) as in \(T^{\prime}\)) if \(K=N_{H}(x)\) and by adding node \(K^{\prime}\) and edge \(KK^{\prime}\) otherwise. Then, \(T\) is a clique tree of \(H\). Let us show that the nodes of \(T\) are the maximal cliques of \(H\). As \(x\) is simplicial in \(H\), \(K^{\prime}\) is the unique maximal clique of \(H\) containing \(x\). Each maximal clique of \(H\) different from \(K^{\prime}\) is a maximal clique of \(H^{\prime}\), and each maximal clique of \(H^{\prime}\) different from \(N_{H}(x)\) is a maximal clique of \(H\). It follows that the nodes of \(T\) are the maximal cliques of \(H\). It remains to show that for each vertex \(y\) of \(H\), the subgraph \(T_{y}\) of \(T\) induced by the set of nodes of \(T\) containing \(y\) is connected. If \(y=x\), then \(T_{y}\) is reduced to node \(K^{\prime}\); otherwise, \(T_{y}\) is either equal to \(T_{y}^{\prime}\) or obtained from \(T_{y}^{\prime}\) by replacing node \(K\) by node \(K^{\prime}\) or by nodes \(K\) and \(K^{\prime}\) and edge \(KK^{\prime}\). Hence, \(T_{y}\) is connected. The following proposition is an invariant of the **for** loop of the algorithm CliqueTree:  
\((\{K_{1},\ldots,K_{s}\},\{K_{p}K_{q},\ (p,q)\in E\})\) is a clique tree of \(H(V^{\prime})\),  
\((\)b\()\): _Sep is the set of minimal separators of \(H(V^{\prime})\),_  
\((\)c\()\): \(\forall y\in V^{\prime}\)_,_ \(clique(y)\in[1,s]\) _and_ \(N_{H}^{\pm+}[y]\subseteq K_{clique(y)}\)_._  
The proposition clearly holds at the initialization step of the **for** loop. Let us show that it is preserved by each iteration of this loop.