# Computing a Clique Tree with the Algorithm Maximal Label Search
## 1 Introduction
The beginning of a new clique is detected by a condition on the labels: as long as the label of the vertex that has just been chosen is strictly greater than the label of the previous vertex, the current clique is increased ; otherwise, a new clique is started. This leads to the two following questions: (1) does MLS compute the maximal cliques one after another? (2) does MLS detect new cliques by a condition on labels? We first consider Question (1). We know that a clique tree of a chordal graph \(H\) can be computed from any PEO of \(H\)[3], but not necessarily by processing one clique after another. We will show that the maximal cliques are computed one clique after another if the PEO is a PMO (perfect complex ordering) of the input chordal graph. A moplex is a clique module whose neighborhood is a minimal separator (thus, in a chordal graph, the closed neighborhood of a moplex is a maximal clique), and a PMO of a graph is an ordering of its vertices obtained by successively removing each vertex of a simplicial moplex of the current graph until it is a clique (a moplex of a chordal graph is necessarily simplicial). [PERSON] and [PERSON] [8] showed that LexBFS ends on a moplex of the input graph whether it is chordal or not, which implies that LexBFS computes a PMO of the input graph if it is chordal. [PERSON], [PERSON], [PERSON] and [PERSON] [12] proved the more general result that any instance of the algorithm MLS with totally ordered labels computes a PMO of a chordal graph. [PERSON] and [PERSON] [13] showed that MCS and LexBFS can be modified to compute the minimal separators and the maximal cliques of a chordal graph, using the fact that the computed ordering is a PMO of this graph, thus extending the result for MCS from [4]. [PERSON], [PERSON] and [PERSON] [14] showed that LexDFS ends on a moplex of the input graph whether it is chordal or not, thus extending the result for LexBFS from [8]. We show in this paper that a slight variant of MLS computes a PMO of the input chordal graph for each labeling structure. As this variant is equivalent to MLS if the order on the labels is total, this generalizes the result from [12] that MLS used with totally ordered labels computes a PMO of a chordal graph. Concerning Question (2), we give a necessary and sufficient condition on a labeling structure for MLS to detect new cliques by a condition on labels. Because this condition is not satisfied by the labeling structure associated with the algorithm LexDFS, the LexDFS labels do not detect new cliques, contrary to what is claimed in [14]. We then go on to examine what happens when the graph is not chordal. When a graph is chordal, the minimal separators are cliques. When the graph fails to be chordal, it still may have clique minimal separators. The related graph decomposition (called clique minimal separator decomposition) has given rise to recent interest; see for example [15; 16; 17; 18; 19]. This decomposition results in a set of overlapping subgraphs called atoms, characterized as the maximal connected subgraphs containing no clique separator. Recent work by [PERSON], [PERSON] and [PERSON] [20] has shown that the atoms of a connected graph can be organized into a tree similar to a clique tree, called an atom tree: the nodes are the atoms, and the edges represent the clique minimal separators of the graph. As is the case for a clique tree, an atom tree has at most \(n\) nodes and less than \(n\) edges. The work in [20] showed how an atom tree can be computed from a clique tree of a minimal triangulation (which is a minimal embedding of a graph into a chordal graph), providing an algorithm based on MCS-M [21], the triangulating counterpart of MCS, to build an atom tree. In this paper, we further address the question of using MLSM, the triangulating counterpart of MLS defined in [10] which is a generalization of MCS-M, to build this atom tree. The main contributions of this paper are the following. We provide a characterization of PMOs (Characterization 3), which is helpful in proofs concerning PMOs.