# Computing a Clique Tree with the Algorithm Maximal Label Search
## 2 Preliminaries
### Algorithms MLS and MLSM  
The algorithm MLS (Algorithm 1), where MLS stands for (Maximal Label Search, generalizes the well-known algorithms MCS from [5], LexBFS from [6] and LexDFS and MNS from [9]. The algorithm MLS takes a graph \(H\) and a labeling structure \(\mathcal{L}\) as input and yields an ordering of \(H\) as output, which is a PEO of \(H\) if \(H\) is chordal. It can be seen as a generic algorithm with parameter \(\mathcal{L}\) whose instances are the algorithms \(\mathcal{L}\)-MLS for each labeling structure \(\mathcal{L}\), with a graph \(H\) as input and an ordering of \(H\) as output. In the following definitions, \(\mathbb{N}^{+}\) denotes the set of positive integers. Definition 3: A labeling structure is a structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\), where:  
* \(L\) is a set (the set of labels),
* \(\preceq\) is a partial order on \(L\) (which may be total or not, with \(\prec\) denoting the corresponding strict order),
* \(l_{0}\) is an element of \(L\) (the initial label),
* \(Inc\) (increase) is a mapping from \(L\times\mathbb{N}^{+}\) to \(L\) satisfying the following IC (Inclusion Condition): for any subsets \(I\) and \(I^{\prime}\) of \(\mathbb{N}^{+}\), if \(I\subset I^{\prime}\), then \(lab_{\mathcal{L}}(I)\prec lab_{\mathcal{L}}(I^{\prime})\), where \(lab_{\mathcal{L}}(I)=Inc(\ldots(Inc(l_{0},i_{1}),\ldots),i_{k})\), where \(I=\{i_{1},i_{2},\ldots,i_{k}\}\), with \(i_{1}>\cdots>i_{k}\). For each X in {MCS, LexBFS, LexDFS, MNS}, the algorithm X is the instance \(\mathcal{L}_{X}\)-MLS of the algorithm MLS, where \(\mathcal{L}_{X}\) is the labeling structure \((L,\preceq,l_{0},Inc)\) defined as follows. \(\mathcal{L}_{MCS}\): \(L=\mathbb{N}^{+}\cup\{0\}\), \(\preceq\) is \(\leq\) (a total order), \(l_{0}=0\), \(Inc(l,i)=l+1\). \(\mathcal{L}_{LexBFS}\): \(L\) is the set of lists of elements of \(\mathbb{N}^{+}\), \(\preceq\) is the usual lexicographic order (a total order), \(l_{0}\) is the empty list, \(Inc(l,i)\) is obtained from \(l\) by appending \(i\) to the end of the list. \(\mathcal{L}_{LexDFS}\): \(L\) is the set of lists of elements of \(\mathbb{N}^{+}\), \(\preceq\) is the lexicographic order where the order on \(\mathbb{N}^{+}\) is the reverse order of the usual one (a total order), \(l_{0}\) is the empty list, \(Inc(l,i)\) is obtained from \(l\) by prepending \(i\) to the beginning of the list. \(\mathcal{L}_{MNS}\): \(L\) is the power set of \(\mathbb{N}^{+}\), \(\preceq\) is \(\subseteq\) (not a total order), \(l_{0}=\emptyset\), \(Inc(l,i)=l\cup\{i\}\). ```
input : a connected graph \(H\) and a labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\) output : an ordering \(\alpha=(x_{1},\ldots,x_{n})\) of \(H\), which is a PEO of \(H\) if \(H\) is chordal \(V^{\prime}\leftarrow\emptyset\); initialize all labels as \(l_{0}\); for\(i=n\)down to \(1\)do  Choose a vertex \(x\) in \(V\setminus V^{\prime}\) whose label is maximal; \(x_{i}\gets x\); foreach\(y\) in \(N_{H}(x)\setminus V^{\prime}\)do \(label(y)\gets Inc(label(y),i)\);  end for \(V^{\prime}\gets V^{\prime}\cup\{x\}\);  end for
```  
**Algorithm 2**MLSM. The algorithm MLSM (Algorithm 2), where the final letter M stands for MEO, generalizes the algorithms LEX M from [6] and MCS-M from [21]. It takes a graph \(G\) and a labeling structure \(\mathcal{L}\) as input and yields an MEO of \(G\) and the associated minimal triangulation of \(G\) as output. It can be seen as a generic algorithm in the same way as the algorithm MLS. The algorithms LEX M and MCS-M are the instances \(\mathcal{L}_{LexBFS}\)-MLSM and \(\mathcal{L}_{MCS}\)-MLSM, respectively, of the algorithm MLSM.