Optimal decomposition by clique separators

AbstractDecompositions of a graph by clique separators are investigated which have the additional property that they do not generate new maximal prime subgraphs. Using such decompositions is preferable in many applications, since they lead to a minimal system of derived subgraphs. The methods used in the proofs are familiar from the investigations of chordal graphs and acyclic hypergraphs and some well-known results for these (hyper-) graphs are shown to be simple special cases of results for maximal prime subgraphs.Tarjan has described an O(nm)-time algorithm to decompose a graph with n vertices and m edges by means of clique separators. This algorithm is modified, so that no new maximal prime subgraphs are generated, i.e. so that a graph is decomposed exactly into its maximal prime subgraphs which is the unique minimal derived system of prime subgraphs