Characterization and complexity of uniformly nonprimitive labeled 2-structures. (English) Zbl 0873.68161
Summary: According to the clan decomposition theorem of A. Ehrenfeucht and G. Rozenberg [Theor. Comput. Sci. 70, No. 3, 277-303 (1990; Zbl 0701.05051); ibid. 305-342 (1990; Zbl 0701.05052)] each labeled 2-structure has a decomposition into three types of basic 2-structures: complete, linear and primitive. This decomposition can be expressed as a node labeled tree, the shape of the 2-structure. Our main interest is in the uniformly nonprimitive 2-structures, which do not have primitive substructures. Every (directed) graph can be considered as a restricted 2-structure with only two labels (arc, no-arc). It is proved that forbidding primitivity in the 2-structures gives a unified approach to some well-known classes of graphs, viz., the cographs and the transitive vertex series-parallel graphs.
We also study the parallel complexity of the decomposition of 2-structures. It is shown that there is a LOGCF algorithm, which recognizes the uniformly nonprimitive 2-structures and constructs their shapes. We prove also that for every MSO (monadic second-order) definable property of 2-structures, there is a LOGCF algorithm to decide whether or not a uniformly nonprimitive 2-structure has that property.
We also study the parallel complexity of the decomposition of 2-structures. It is shown that there is a LOGCF algorithm, which recognizes the uniformly nonprimitive 2-structures and constructs their shapes. We prove also that for every MSO (monadic second-order) definable property of 2-structures, there is a LOGCF algorithm to decide whether or not a uniformly nonprimitive 2-structure has that property.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Keywords:
parallel complexity of the decomposition of 2-structures; LOGCF algorithm; MSO (monadic second-order) definable propertyReferences:
| [1] | Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebra. Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022 |
| [2] | Arnborg, S.; Corneil, D. G.; Proskurowski, A., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1-19 (1990) · Zbl 0701.05016 |
| [3] | Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073 |
| [4] | Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. Algebra Discrete Methods, 7, 305-314 (1986) · Zbl 0597.05027 |
| [5] | Birnbaum, Z. W.; Esary, J. D., Modules of coherent binary systems, SIAM J. Appl. Math., 13, 444-462 (1965) · Zbl 0235.94029 |
| [6] | Bodlaender, H. L., NC-algorithms for graphs with small treewidth, (Proc. WG’88. Proc. WG’88, Lecture Notes in Computer Science, Vol. 344 (1989), Springer: Springer Berlin), 1-10 · Zbl 1533.68211 |
| [7] | Bondy, J. A.; Murthy, U. S.R., Graph Theory with Applications (1978), Macmillan: Macmillan London |
| [8] | Bonizzoni, P., Primitive 2-structures with the \((n\) − 2)-property, Theoret. Comput. Sci., 132, 151-178 (1994) · Zbl 0822.68078 |
| [9] | Buer, H.; Möhring, R. H., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, 170-184 (1983) · Zbl 0517.05057 |
| [10] | Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043 |
| [11] | Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 138-154 (1975) · Zbl 0277.05139 |
| [12] | Corneil, D. G.; Lerch, H.; Stewart-Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057 |
| [13] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85, 12-75 (1990) · Zbl 0722.03008 |
| [14] | Courcelle, B., The monadic second-order logic of graphs. III. Tree-decompositions, minors, and complexity issues, RAIRO Theoret. Inform. Appl., 26, 257-286 (1992) · Zbl 0754.03006 |
| [15] | Courcelle, B., The monadic second-order logic of graphs. V. On closing the gap between definability and recognizability, Theoret. Comput. Sci., 80, 153-202 (1991) · Zbl 0754.68065 |
| [16] | Courcelle, B., The monadic second-order logic of graphs. VI. On several representations of graphs by relational structures, Discrete Appl. Math., 54, 117-149 (1994) · Zbl 0809.03005 |
| [17] | Doner, J., Tree acceptors and some of their applications, J. Comput. System. Sci., 4, 406-451 (1970) · Zbl 0212.02901 |
| [18] | A. Ehrenfeucht, H.N. Gabow, R.M. McConnell and S.J. Sullivan, An \(On^2 J. Algorithms \); A. Ehrenfeucht, H.N. Gabow, R.M. McConnell and S.J. Sullivan, An \(On^2 J. Algorithms \) |
| [19] | Ehrenfeucht, A.; Harju, T.; Rozenberg, G., Incremental construction of 2-structure, Discrete Math., 128, 113-141 (1994) · Zbl 0796.05083 |
| [20] | Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, Part I, Theoret. Comput. Sci., 70, 277-303 (1990) · Zbl 0701.05051 |
| [21] | Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, Part II, Theoret. Comput. Sci., 70, 305-342 (1990) · Zbl 0701.05052 |
| [22] | Ehrenfeucht, A.; Rozenberg, G., Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., 70, 343-358 (1990) · Zbl 0701.05053 |
| [23] | Ehrenfeucht, A.; Rozenberg, G., Angular 2-structures, Theoret. Comput. Sci., 92, 227-248 (1992) · Zbl 0753.05069 |
| [24] | Engelfriet, J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, (Graph-Grammars and their Application to Computer Science. Graph-Grammars and their Application to Computer Science, Lecture Notes in Computer Science, Vol. 532 (1991), Springer: Springer Berlin), 311-327 · Zbl 0765.68090 |
| [25] | Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66 (1967) · Zbl 0153.26002 |
| [26] | Garey, M. R.; Johnson, D. S., (Computers and Intractability, a Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco) · Zbl 0411.68039 |
| [27] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [28] | Gécseg, F.; Steinby, M., Tree Automata (1984), Akadémiai Kiadó: Akadémiai Kiadó Budapest · Zbl 0396.68041 |
| [29] | Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 |
| [30] | Harju, T.; Rozenberg, G., Reductions for primitive 2-structures, Fundam. Inform., 20, 133-144 (1994) · Zbl 0798.05068 |
| [31] | Harju, T.; Rozenberg, G., Decomposition of infinite labeled 2-structures, (Lecture Notes in Computer Science, Vol. 812 (1994), Springer: Springer Berlin), 145-158 · Zbl 1529.68211 |
| [32] | Immermann, N., Nondeterministic space is closed under complement, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056 |
| [33] | Kaerkes, R., Netzplan theorie, Oper. Res. Verfaren, 27, 1-65 (1977) · Zbl 0428.90019 |
| [34] | Kozen, D.; Vazirani, U. V.; Vazirani, V. V., NCNC algorithms for comparability graphs, interval graphs, and unique perfect matchings, (Tech. Report TR 86-799 (1986), Cornell University: Cornell University Ithaca, NY) · Zbl 0598.68050 |
| [35] | Lautemann, C., Decomposition trees: structured graph representation and efficient algorithms, (Proc. CAAP’88. Proc. CAAP’88, Lecture Notes in Computer Science, Vol. 299 (1988), Springer: Springer Berlin), 28-39 · Zbl 0645.68074 |
| [36] | Lautemann, C., The complexity of graph languages generated by hyperedge replacement, Acta Inform., 27, 399-421 (1990) · Zbl 0725.68055 |
| [37] | Lautemann, C., Tree automata, tree decomposition, and hyperedge replacement, (Report No. 2/90 (1990), Johannes Gutenberg University: Johannes Gutenberg University Mainz) · Zbl 0765.68160 |
| [38] | Lin, R.; Olariu, S., An NC recognition algorithm for cographs, J. Parallel Distrib. Comput., 13, 76-90 (1991) |
| [39] | R.M. McConnell, A linear-time incremental algorithm to compute the prime tree family of a 2-structure, Algoritmica; R.M. McConnell, A linear-time incremental algorithm to compute the prime tree family of a 2-structure, Algoritmica |
| [40] | Moon, J. W., Embedding tournaments in simple tournaments, Discrete Math., 2, 389-395 (1972) · Zbl 0236.05108 |
| [41] | Möhring, R. H.; Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization, Ann. Discrete Math., 19, 257-356 (1984) · Zbl 0567.90073 |
| [42] | Muller, J. H.; Spinrad, J., Incremental modular decomposition, J. ACM, 36, 1-19 (1989) · Zbl 0671.68030 |
| [43] | Müller, V.; Nešetřil, J.; Pelant, J., Either tournaments or algebras?, Discrete Math., 11, 37-66 (1975) · Zbl 0301.05114 |
| [44] | Novick, M. B., Fast parallel algorithms for the modular decomposition, (Tech. Report TR 89-1016 (1989), Cornell University: Cornell University Ithaca, NY) |
| [45] | Proskurowski, A.; Sysło, M. M., Computations in tree-like graphs, Comput. Suppl., 7, 1-19 (1990) · Zbl 0713.68034 |
| [46] | Robertson, N.; Seymour, P., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017 |
| [47] | Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 218-235 (1980) · Zbl 0445.68034 |
| [48] | Ruzzo, W. L., On uniform circuit complexity, J. Comput. System Sci., 22, 365-383 (1981) · Zbl 0462.68013 |
| [49] | 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 |
| [50] | Spinrad, J.; Valdez, J., Recognition and isomorphism of two dimensional partial orders, (Lecture Notes in Computer Science, Vol. 154 (1983), Springer: Springer Berlin), 676-686 · Zbl 0521.68081 |
| [51] | Sudborough, I. H., On the tape complexity of deterministic context-free languages, J. ACM, 25, 405-414 (1978) · Zbl 0379.68054 |
| [52] | Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279-284 (1988) · Zbl 0638.68046 |
| [53] | Sumner, D. P., Graphs indecomposable with respect to the \(X\)-join, Discrete Math., 6, 281-298 (1973) · Zbl 0279.05125 |
| [54] | Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem of second-order logic, Math. Systems. Theory, 2, 57-81 (1968) · Zbl 0157.02201 |
| [55] | Valdez, J.; Tarjan, R. E.; Lawler, E., The recognition of series parallel digraphs, SIAM J. Computing, 11, 298-313 (1982) · Zbl 0478.68065 |
| [56] | Wald, A.; Colbourn, C. J., Steiner trees, partial 2-trees and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036 |
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.
