## 3 Search Algorithms
### Algorithms MLS and MLSM  
The definitions of Algorithms MLS and MLSM are based on the notion of _labeling structure_.  
**Definition 3.1**: _[_12_]_ _A **labeling structure** is a four-tuple \((L,\preceq,l_{0},Inc)\), where:_  
* \(L\) _is a finite set of labels,_
* \(\preceq\) _is a partial order on_ \(L\)_, with_ \(\prec\) _denoting the corresponding strict order,_
* \(l_{0}\) _is an element of_ \(L\)_,_
* \(Inc\) _is a mapping from_ \(L\times\{2,3,...\}\) _to_ \(L\) _such that:_ _for any integer_ \(i>1\) _and for any labels_ \(l\) _and_ \(l^{\prime}\)_,_ _the following properties hold:_ 1. \(l\prec Inc(l,i)\)__ 2. _if_ \(l\prec l^{\prime}\) _then_ \(Inc(l,i)\prec Inc(l^{\prime},i)\)__  
The order \(\preceq\) is used to choose a vertex of maximal label, \(l_{0}\) to initialize the labels, and \(Inc\) to increment labels.  
Algorithms MLS and MLSM are given below.  
```
input : A graph \(G=(V,E)\) and a labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\). output : An ordering \(\alpha\) on \(V\), which is a peo of \(G\) if \(G\) is chordal.  Initialize all labels as \(l_{0}\); \(G^{\prime}\gets G\); for\(i=n\) downto\(1\)do  Choose a vertex \(x\) of \(G^{\prime}\) with maximal label; \(\alpha(i)\gets x\); foreach\(y\) in \(N_{G^{\prime}}(x)\)do \(label(y)\gets Inc(label(y),i)\);  Remove \(x\) from \(G^{\prime}\);
```  
**Algorithm MLSM** (Maximal Label Search for Meo)[12]  
```
input : A graph \(G=(V,E)\) and a labeling structure \(\mathcal{L}=(L,\preceq,l_{0},Inc)\). output : An meo \(\alpha\) on \(V\) and a minimal triangulation \(H=G_{\alpha}^{+}\) of \(G\).  Initialize all labels as \(l_{0}\); \(E^{\prime}\gets E\); \(G^{\prime}\gets G\); for\(i=n\) downto \(1\)do  Choose a vertex \(x\) of \(G^{\prime}\) of maximal label; \(\alpha(i)\gets x\); foreach vertex \(y\) of \(G^{\prime}\) different from \(x\)do ifthere is a path from \(x\) to \(y\) in \(G^{\prime}\) such that every internal vertex on the path has a label strictly smaller than \(label(y)\)then \(E^{\prime}\gets E^{\prime}\cup\{xy\}\); foreach\(y\) in \(V\) such that \(xy\in E^{\prime}\)do \(label(y)\gets Inc(label(y),i)\); Remove \(x\) from \(G^{\prime}\); \(H\leftarrow(V,E^{\prime})\);
```  
When using labeling structure \(\mathcal{L}\) with MLS (respectively MLSM), we will refer to the algorithm as \(\mathcal{L}\)-MLS (respectively \(\mathcal{L}\)-MLSM). We call any ordering on \(V\) that can be produced by MLS (respectively MLSM, \(\mathcal{L}\)-MLS, \(\mathcal{L}\)-MLSM) an MLS (respectively MLSM, \(\mathcal{L}\)-MLS, \(\mathcal{L}\)-MLSM) ordering.  
The following Property was proved in [12]:  
**Property 3.2**: _([12] ) For any graph \(G\) and any labeling structure \(\mathcal{L}\), Algorithm \(\mathcal{L}\)-MLSM computing ordering \(\alpha\) on \(G\) has the same behavior as \(\mathcal{L}\)-MLS on \(G_{\alpha}^{+}\). That is, they give the same labels and numbers to vertices, provided that they break ties in the same way._  
Property 3.2 has two important consequences that are used in this paper:  
**Consequence 1:** Any \(\mathcal{L}\)-MLSM ordering \(\alpha\) of \(G\) is a \(\mathcal{L}\)-MLS ordering of \(G_{\alpha}^{+}\). Thus a property of MLS on chordal graphs can in some cases be extended to a property of MLSM on arbitrary graphs since \(G_{\alpha}^{+}\) is chordal (This is used in Theorem 4.1 and in Property 4.5).  
**Consequence 2:** MLS and MLSM have the same behavior on a chordal graph, since in that case, \(G_{\alpha}^{+}=G\). Any execution of MLS on a chordal graph can be seen as an execution of MLSM, and conversely. Thus any property of MLSM on arbitrary graphs also holds for MLS on chordal graphs.