Nesting of prime substructures in \(k-\)ary relations. (English) Zbl 0973.68185
Summary: The modular decomposition of a graph or relation has a large number of combinatorial applications. It divides the structure into a set of “prime” induced substructures, which cannot be further decomposed. Recent work on graphs and \(k\)-ary relations has focused on the discovery that prime induced substructures are densely nested when they occur. Lower bounds on the “nesting density” of prime substructures in graphs are used heavily in the only known linear-time algorithm for directed graphs. We improve on the previously known lower bounds for \(k\)-ary relations, and show that no further improvement is possible.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
modular decomposition of a graphReferences:
| [1] | Bonizzoni, P., Primitive 2-structures with the \((n−2)\)-property, Theoret. Comput. Sci., 132, 151-178 (1994) · Zbl 0822.68078 |
| [2] | P. Bonizzoni, A tight lower bound for Primitivity in \(k\); P. Bonizzoni, A tight lower bound for Primitivity in \(k\) · Zbl 1418.68163 |
| [3] | A. Cournier, M. Habib, An efficient algorithm to recognize prime undirected graphs, Technical Report R.R. LIRMM 92-023, Laboratoire D’Informatique, de Robotique et de Microelectronique de Montpellier, 1992.; A. Cournier, M. Habib, An efficient algorithm to recognize prime undirected graphs, Technical Report R.R. LIRMM 92-023, Laboratoire D’Informatique, de Robotique et de Microelectronique de Montpellier, 1992. · Zbl 0925.05051 |
| [4] | Cournier, A.; Habib, M., A new linear algorithm for modular decomposition, (Tison, S., CAAP’94: 19th Int. Colloq., Lecture Notes in Computer Science (1994), Springer: Springer Berlin, Edinburgh, UK), 68-82 · Zbl 0938.05502 |
| [5] | Ehrenfeucht, A.; McConnell, R. M., A \(k\)-structure generalization of the theory of 2-structures, Theoret. Comput. Sci., 132, 209-227 (1994) · Zbl 0808.05089 |
| [6] | Ehrenfeucht, A.; Rozenberg, G., Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., 70, 343-358 (1990) · Zbl 0701.05053 |
| [7] | J. Engelfriet, T. Harju, A. Proskurowski, G. Rozenberg, Survey on graphs as 2-structures and parallel complexity of decomposition, Technical Report 93-06, Department of Computer Science, Leiden University, Leiden, 1993.; J. Engelfriet, T. Harju, A. Proskurowski, G. Rozenberg, Survey on graphs as 2-structures and parallel complexity of decomposition, Technical Report 93-06, Department of Computer Science, Leiden University, Leiden, 1993. |
| [8] | Gallai, T., Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66 (1967) · Zbl 0153.26002 |
| [9] | Kelly, D., Comparability graphs, (Rival, I., Graphs and Order (1985), D. Reidel: D. Reidel Boston), 3-40 |
| [10] | McConnell, R. M.; Spinrad, J. P., Modular decomposition and transitive orientation, Discrete Math., 201, 1-3, 189-241 (1999) · Zbl 0933.05146 |
| [11] | R.M. McConnell, J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proc. Fifth Ann. ACM-SIAM Symp. on Discrete Algorithms, Arlington, VI, 1994, pp. 536-545.; R.M. McConnell, J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proc. Fifth Ann. ACM-SIAM Symp. on Discrete Algorithms, Arlington, VI, 1994, pp. 536-545. · Zbl 0867.05068 |
| [12] | Moehring, R. H., Algorithmic aspects of comparability graphs and interval graphs, (Rival, I., Graphs and Orders (1985), D. Reidel: D. Reidel Boston), 41-101 · Zbl 0569.05046 |
| [13] | R.H. Moehring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions, Ann. Oper. Res. 4 (1985/6) 195-225.; R.H. Moehring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions, Ann. Oper. Res. 4 (1985/6) 195-225. |
| [14] | Sabidussi, G., Graph derivatives, Math. Z., 76, 385-401 (1961) · Zbl 0109.16404 |
| [15] | Schmerl, J. H.; Trotter, W. T., Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113, 191-205 (1993) · Zbl 0776.06002 |
| [16] | Sumner, D. P., Graphs indecomposable with respect to the \(x\)-join, Discrete Math., 6, 281-298 (1973) · Zbl 0279.05125 |
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.
