# Computing a Clique Tree with the Algorithm Maximal Label Search
## 1 Introduction  
Chordal graphs form an important and well-studied graph class, have many characterizations and properties and are used in many applications. From an algorithmic point of view, connected chordal graphs are endowed with a compact representation as a clique tree, which organizes both the maximal cliques (which are the nodes of the tree) and the minimal separators (which label the edges): in a chordal graph, a minimal separator is the intersection of two maximal cliques, so each minimal separator is a clique (a characterization of chordal graphs [1]). Since a connected chordal graph has at most \(n\) maximal cliques, a clique tree has at most \(n\) nodes and less than \(n\) edges, a very efficient representation of the underlying chordal graph. A PEO (perfect elimination ordering) of a graph is an ordering of its vertices obtained by successively removing a simplicial vertex of the current graph (a vertex is simplicial if its neighborhood is a clique). A clique tree of a chordal graph can be computed efficiently using the characterization of a chordal graph as a graph, which has a PEO [2]. [PERSON] [3] showed how to compute a clique tree from an arbitrary PEO of the input chordal graph. [PERSON] and [PERSON] [4] proposed an algorithm based on the search algorithm MCS (Maximum Cardinality Search) from [5], using the properties of both the PEO and the labels computed by MCS to build a clique tree in a simple and elegant way. The algorithm MCS numbers the vertices using labels that count the number ofprocessed neighbors. MCS, as well as its famous cousin LexBFS (Lexicographic Breadth-First Search) from [6] were originally tailored to compute a PEO of the input graph if it is chordal, thus leading to an efficient algorithm recognizing chordal graphs. Recent work by [PERSON] and [PERSON] [7] showed how MCS defines the minimal separators of a chordal graph. LexBFS was also shown to scan both the maximal cliques and the minimal separators of a chordal graph [8]. This family of search algorithms has been recently extended by [PERSON] and [PERSON] [9], who introduced LexDFS (Lexicographic Depth-First Search) and MNS (Maximal Neighborhood Search). All of these algorithms function on the same basic principle: they use a labeling process to compute an ordering of the vertices of the input graph. All vertex labels are initialized with the same initial label. At each iteration of the algorithm, a yet unnumbered vertex with a maximal label is chosen, and the labels of its yet unnumbered neighbors are increased. [PERSON], [PERSON] and [PERSON] [10] introduced the algorithm MLS (Maximal Label Search) as a generalization of these algorithms. MLS takes as input a graph \(G\) and a labeling structure \(\mathcal{L}\) and computes an ordering of the vertices of \(G\), which is a PEO of \(G\) if \(G\) is chordal. A condition on the definition of a labeling structure from [10] ensures that MLS computes a PEO of a chordal graph. A still more general labeling search algorithm called GLS (General Label Search) was defined in [11] from a more general definition of a labeling structure, which captures classical categories of graph searches (general search, breadth-first and depth-first searches) in addition to the graph searches derived from MLS. The question we address in this paper is to determine in which cases MLS can be used to build a clique tree. Our goal is not to improve the time complexity of computing a clique tree, since this complexity is already known to be linear, but to further investigate the algorithm MLS and the properties of the labeling structures involved, in order to determine how MLS can be used to compute a clique tree. To accomplish this, we first focus on the algorithm from [4], extended-MCS, which computes a clique tree of a chordal graph by computing the maximal cliques of \(H\) one after another.