We address the problem of computing the atoms of the decomposition by clique minimal separators of a graph G (also called the maximal prime subgraphs) when a minimal triangulation H of G is given as part of the input. We present a new algorithmic technique based on the clique tree of H. We introduce a new graph parameter, m0, which is the number of edges belonging to no minimal separator of H. We give an algorithm which runs in O(nm0) time, which improves the current O(nm) time for this problem. Another version of our algorithm runs in O(n(n+t)) time, where t is the number of 2-pairs of H. We show that our technique computes the atoms in O(n2) time for several graph classes, including the graphs with bounded treewidth, which improves the current O(n3) time for dense graphs by a factor of n.
