×

zbMATH — the first resource for mathematics

Decomposition by clique separators. (English) Zbl 0572.05039
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 J. E. Hopcroft and 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).}
Reviewer: P.Stavre

MSC:
05C38 Paths and cycles
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[3] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[4] Edmonds, J., Matching and a polyhedron with 0-1 vertices, J. res. nat. bur. standards, 69B, 125-130, (1965) · Zbl 0141.21802
[5] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton University Press Princeton, NJ · Zbl 0139.13701
[6] Frank, A., Some polynomial algorithms for certain graphs and hypergraphs, (), 211-226, Congressus Numeratium XV
[7] Fulkerson, D.R.; Gross, O., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[9] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[10] Gavril, F., Algorithms on clique separable graphs, Discrete math., 19, 159-165, (1977) · Zbl 0378.05042
[11] M.C. Golumbic and R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B, to appear. · Zbl 0537.05063
[12] Golumbic, M.C.; Jamison, R.E., Edge and vertex intersection of paths in trees, Discrete math., 55, 151-159, (1985) · Zbl 0568.05023
[13] Hopcroft, J.E.; Tarjan, R.E., Dividing a graph into triconnected components, SIAM J. comput., 2, 135-158, (1973) · Zbl 0281.05111
[14] Holyer, I., The NP-completeness of edge coloring, SIAM J. comput., 10, 718-720, (1981) · Zbl 0473.68034
[15] Lehot, P.G.H., An optimal algorithm to detect a line graph and output its root graph, J. ACM, 21, 569-575, (1974) · Zbl 0295.05118
[16] Lipton, R.J.; Tarjan, R.E., A separator theorem for planar graphs, SIAM, J. appl. math., 36, 177-189, (1979) · Zbl 0432.05022
[17] Ohtsuki, T.; Cheung, L.K.; Fujisawa, T., Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, J. math. anal. appl., 54, 622-633, (1976) · Zbl 0371.65006
[18] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[19] Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definitive systems of linear equations, (), 183-217
[20] Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[21] Shannon, C.E., A theorem on coloring the lines of a network, J. math. phys., 28, 148-151, (1949) · Zbl 0032.43203
[22] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 623-641, (1982) · Zbl 0485.68055
[23] Tarjan, R.E., Depth-first search and linear graph algorithms, SIAM J. comput., 1, 146-160, (1972) · Zbl 0251.05107
[24] Vizing, V.G., On an estimate of the chromatic class of a p-graph (in Russian), Diskret. analiz., 3, 25-30, (1964)
[25] Whitesides, S.H., An algorithm for finding clique cut-sets, Inform. proc. letters, 12, 31-32, (1981) · Zbl 0454.68078
[26] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebraic discrete meth., 2, 77-79, (1981) · Zbl 0496.68033
[27] Monma, C.L.; Wei, V.K., Intersection graphs of paths in a tree, (1985), Bell Communications Research Morristown, NJ · Zbl 0682.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.