# Computing a Clique Tree with the Algorithm Maximal Label Search
## 5 Extended Results
### Atom Tree and Clique Minimal Separators  
An atom tree of a connected graph \(G\) can be computed from a clique tree of a minimal triangulation of \(G\) as described in the following theorem.  
Theorem 9: _[_20_]_ _Let \(G\) be a connected graph; let \(H\) be a minimal triangulation of \(G\); let \(T=(V_{T},E_{T})\) be a clique tree of \(H\); and let \(T^{\prime}\) be the forest obtained from \(T\) by removing all edges \(KK^{\prime}\) such that \(K\cap K^{\prime}\) is a clique in \(G\); let \(T^{\prime\prime}\) be the tree obtained from \(T\) by merging the nodes of each tree of \(T^{\prime}\) into one node; then, \(T^{\prime\prime}\) is an atom tree of \(G\), and for each edge \(KK^{\prime}\) of \(T\) such that \(K\cap K^{\prime}\) is a clique in \(G\), \(K\cap K^{\prime}=A\cap A^{\prime}\), where \(A\) and \(A^{\prime}\) are the atoms of \(G\) containing \(K\) and \(K^{\prime}\), respectively._  
Thus, the algorithm DCL-MLSM-CliqueTree can be modified into the algorithm DCL-MLSM-AtomTree computing an atom tree and the clique minimal separators of the input graph \(G\): in case a new clique is started, a new atom is started only if \(S\) is a clique in \(G\); otherwise, the atom containing \(K_{p}\) is increased. Note that the atoms are not built one after another, since an atom different from \(A_{s}\) may be increased if a new clique is started and \(S\) is not a clique in \(G\). Variable \(q\) contains the index of the current atom. The algorithm DCL-MLSM-AtomTree (Algorithm 12) generalizes the algorithm MCSM-atom-tree from [20], while correcting an error in this algorithm (a confusion between variables \(q\) and \(s\)).  
**InitAT** // _Initialize the Atom Tree_  
\(V^{\prime}\leftarrow\emptyset\)_;_ \(s\gets 1\)_;_ \(a\gets 1\)_;_ \(A_{1}\leftarrow\emptyset\)_;_ \(E\leftarrow\emptyset\)_;_ \(CliqueSep\leftarrow\emptyset\)_;_  
**StartAtom** // _Start a new Atom_  
\(s\gets s+1\)_;_ \(A_{s}\gets S\)_;_  
\(E\gets E\cup\{(p,s)\}\)_;_ \(CliqueSep\gets CliqueSep\cup\{S\}\)_;_  
**IncreaseAtom** // _Increase the current Atom_  
\(A_{q}\gets A_{q}\cup\{x\}\)_;_ \(atom(x)\gets q\)_;_  
**DefineAT** // _Define the Atom Tree_  
\(T\leftarrow(\{A_{1},\ldots,A_{s}\},\{A_{p}A_{q},\ (p,q)\in E\})\)_;_  
```
input : a connected graph \(G\) and a DCL labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\) output : an atom tree \(T\) and the set \(CliqueSep\) of clique minimal separators of \(G\) \(H\gets G\); InitAT;  Initialize all labels as \(l_{0}\); prev-max-label \(\leftarrow\)\(l_{0}\); for\(i=n\) dawn 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\); \(S\gets N_{H}(x)\cap V^{\prime}\); // \(S=N_{H}^{x+}(x)\) ifprev-max-label \(\
ot\prec label(x)\) and \(i<n\)then \(k\leftarrow\textit{min}\{j,\alpha(j)\in S\}\); \(p\gets clique(\alpha(k))\); if\(S\) is a clique in \(G\)then StartAtom; \(q\gets s\);  end if else \(q\gets p\);  end if  end for IncreaseAtom; \(Y\leftarrow\emptyset\); foreach\(y\) in \(V\setminus V^{\prime}\)do ifthere is a path \(\mu\) of length \(\geq 1\) in \(G(V\setminus V^{\prime})\) between \(x\) and \(y\) such that for each internal vertex \(z\) of \(\mu\) label\((z)\prec label(y)\)then \(Y\gets Y+\{y\}\); \(E(H)\gets E(H)\cup\{xy\}\);  end if foreach\(y\) in \(Y\)do \(label(y)\gets Inc(label(y),i)\);  end for \(V^{\prime}\gets V^{\prime}\cup\{x\}\); prev-max-label \(\leftarrow\) label\((x)\);  end for  end foreach\(\textbf{DefineAT}\);
```  
**Algorithm 12**DCL-MLSM-AtomTree.  
The correctness of the algorithm DCL-MLSM-AtomTree follows from Theorem 9, Characterization 2 and from the correctness of the algorithm DCL-MLSM-CliqueTree.