Decomposition by clique separators (Q1062072): Difference between revisions

In this paper the author introduces an interesting theory of decomposition by clique separators which is related to the theory of elimination orderings. The main result is an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. The solvability of this algorithm is proved and it is used in application to NP-complete problems. In Section 4 are given the classes of graphs decomposable by clique separators. \{Reviewer's remark: It is possible that there is a relation with the results of \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [Isomorphism of planar graphs. Complexity of computer computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, York town Heights N.Y. 1972; 131-152; 187- 212 (1972).\}