×
Leimer, Hanns-Georg

Optimal decomposition by clique separators. (English) Zbl 0793.05128

Discrete Math. 113, No. 1-3, 99-123 (1993).
Decompositions of graphs by means of clique separators have been studied by 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)\).
Reviewer: P.Hell (Burnaby)

Cited in 57 Documents

MSC:

05C99 Graph theory
05C90 Applications of graph theory
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

prime subgraphs; clique separators; decompositions

Citations:

Zbl 0572.05039
PDFBibTeX XMLCite
\textit{H.-G. Leimer}, Discrete Math. 113, No. 1--3, 99--123 (1993; Zbl 0793.05128)
Full Text: DOI

References:

[1] Andersen, A. H., Multidimensional Contingency Tables, Scand. J. Statist., 1, 115-127 (1974) · Zbl 0307.62039
[2] Beeri, C.; Fagin, R.; Maie, D.; Mendelson, A.; Ullman, J.; Yannakakis, M., Properties of acyclic database schemes, Proc. 13th Annual ACM Symposium on the Theory of Computing, Assoc. Comput. Mach., 355-362 (1981), New York, Milwaukee
[3] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. Assoc. Comput. Mach., 30, 479-513 (1983) · Zbl 0624.68087
[4] Darroch, J. N.; Lauritzen, S. L.; Speed, T. P., Markov fields and log-linear interaction models for contingency tables, Ann. Statist., 8, 522-539 (1980) · Zbl 0444.62064
[5] Diestel, R., Simplicial decompositions of graphs – some uniqueness results, J. Combin. Theory Ser. B, 42, 133-145 (1987) · Zbl 0582.05045
[6] R. Diestel, Simplicial decompositions of graphs: a survey of applications, submitted.; R. Diestel, Simplicial decompositions of graphs: a survey of applications, submitted. · Zbl 0669.05053
[7] R. Diestel, Simplicial tree-decompositions of infinite graphs I, J. Combin. Theory Ser. B, to appear.; R. Diestel, Simplicial tree-decompositions of infinite graphs I, J. Combin. Theory Ser. B, to appear. · Zbl 0722.05050
[8] R. Diestel, Simplicial tree-decompositions of infinite graphs II—the existence of prime decompositions, J. Combin. Theory Ser. B, to appear.; R. Diestel, Simplicial tree-decompositions of infinite graphs II—the existence of prime decompositions, J. Combin. Theory Ser. B, to appear. · Zbl 0722.05051
[9] R. Diestel, Simplicial tree-decompositions of infinite graphs III—the uniqueness of prime decompositions, J. Combin. Theory Ser. B, to appear.; R. Diestel, Simplicial tree-decompositions of infinite graphs III—the uniqueness of prime decompositions, J. Combin. Theory Ser. B, to appear. · Zbl 0714.05048
[10] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[11] Dirac, G. A., Simplicial decomposition of finite graphs (1984), unpublished manuscript
[12] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001
[13] Haberman, S. J., The Analysis of Frequency Data, (IMS Monographs (1974), Univ. Chicago Press: Univ. Chicago Press Chicago) · Zbl 0325.62017
[14] Halin, R., Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen, Math. Ann., 156, 216-225 (1964) · Zbl 0125.11605
[15] Lauritzen, S. L.; Speed, T. P.; Vijayan, K., Decomposable graphs and hypergraphs, J. Austral. Math. Soc. Ser. A, 36, 12-29 (1984) · Zbl 0533.05046
[16] Lauritzen, S. L.; Wermuth, N., Graphical models for associations between variables, some of which are qualitative and some quantitative, Ann. Statist., 17, 31-57 (1989) · Zbl 0669.62045
[17] Leimer, H. G., Strongly decomposable graphs and hypergraphs, (Res. report 85-1 (1985), Fachbereich Mathematik, Univ. Mainz: Fachbereich Mathematik, Univ. Mainz FRG) · Zbl 0678.05056
[18] Leimer, H. G., Triangulated graphs with marked vertices, (Anderson, L. D., Graph Theory in Memory of G.A. Dirac, Ann. Discrete Math., 41 (1989)), 311-324 · Zbl 0678.05056
[19] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fund. Math. Polska Akad. Nauk, 51, 45-64 (1962) · Zbl 0105.17501
[20] Ohtsuki, T., A fast algorithm for finding an optimal ordering for vertex elimination on a graph, SIAM J. Comput., 5, 133-145 (1976) · Zbl 0353.65018
[21] 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
[22] Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602
[23] 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
[24] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[25] Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062
[26] Vorob’ev, N. N., Consistent families of measures and their extensions, Theor. Prob. Appl., 7, 147-163 (1962) · Zbl 0201.49102
[27] Wagner, K.; Halin, R., Homomorphiebasen von Graphenmengen, Math. Ann., 147, 126-142 (1962) · Zbl 0112.14804
[28] Whittaker, J., Factorisation model formulae and irreducible components of log-linear models (1986), unpublished manuscript
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.