Optimal decomposition by clique separators (Q2366013)

Decompositions of graphs by means of clique separators have been studied by \textit{R. E. Tarjan} [Discrete Math. 55, 221-232 (1985; Zbl 0572.05039)] and others, and have many applications. These decompositions are not generally unique. The author introduces a particular kind of decomposition by clique separators which does result in a unique set of final graphs---these being the maximal subgraphs themselves free of clique separators. He also modifies the algorithm of Tarjan to produce this special decomposition, in time \(O(mn)\).