×

\(P_ 4\)-trees and substitution decomposition. (English) Zbl 0758.68036

Cotrees for cographs (\(P_ 4\)-free graphs) are generalized to \(P_ 4\)- trees, which can be used to give the modular decomposition of the graph. A vertex addition algorithm is given to construct the \(P_ 4\)-tree of an \(n\)-vertex \(m\)-edge graph in \(O(n+m)\) time. A second algorithm is then given to produce the modular decomposition of the graph in almost linear time. A very clear summary of the applications of modular decomposition is included.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Chein, M.; Habib, M.; Maurer, M. C., Partitive hypergraphs, Discrete Math., 37, 35-50 (1981) · Zbl 0478.05071
[3] Colbourne, C. J., On testing isomorphism of permutation graphs, Networks, 11, 13-21 (1981) · Zbl 0459.68031
[4] Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart, Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057
[5] Corneil, D. G.; Perl, Y.; Stewart, L. K., A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934 (1985) · Zbl 0575.68065
[6] Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebraic Discrete Methods, 3, 214-228 (1982) · Zbl 0497.05031
[7] Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, Proceedings of the 15th Annual ACM Symposium on the Theory of Computing, 246-251 (1983)
[8] Gallai, T., Transitiv orientbare Graphen, Acta Math. Acad. Sci. Hungar. Tom., 18, 25-66 (1967) · Zbl 0153.26002
[9] Golumbic, M. C., Comparability graphs and a new matroid, J. Combin. Theory Ser. B, 22, 68-90 (1977) · Zbl 0352.05023
[10] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[11] Habib, M.; Maurer, M. C., On the X-join decomposition for undirected graphs, J. Appl. Discrete Math., 3, 198-207 (1979) · Zbl 0439.05041
[12] Hiragushi, T., On the dimension of partially ordered sets, Sci. Rep. Kanazawa Univ., 1, 77-94 (1951)
[13] Lawler, E. L., Sequencing jobs to minimize weighted completion time subject to precedence constraints, (Annals of Discrete Mathematics, 2 (1978), North-Holland: North-Holland Amsterdam), 75-90 · Zbl 0374.68033
[14] Möhring, R. H., Algorithmic aspects of comparability graphs and interval graphs, (Rival, I., Graphs and Order (1985), Kluwer: Kluwer Dordrecht), 41-102 · Zbl 0569.05046
[15] Möhring, R. H., Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions, Ann. Oper. Res., 4, 195-225 (1985/86)
[16] Möhring, R. H., Computationally tractable classes of ordered sets, (Rival, I., Algorithms and Order (1989), Kluwer: Kluwer Dordrecht), 105-194 · Zbl 1261.06003
[17] Möhring, R. H.; Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization, (Annals of Discrete Mathematics, 19 (1984), North-Holland: North-Holland Amsterdam), 257-356 · Zbl 0567.90073
[18] J.H. Muller and J. Spinrad, On-line modular decomposition, to appear.; J.H. Muller and J. Spinrad, On-line modular decomposition, to appear. · Zbl 0671.68030
[19] Sabidussi, G., Graph derivatives, Math. Z., 76, 385-401 (1961) · Zbl 0109.16404
[20] Shevrin, L. N.; Filipov, N. D., Partially ordered sets and their comparability graphs, Siberian Math. J., 11, 497-509 (1970) · Zbl 0214.23303
[21] Sidney, J. B., Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Oper. Res., 23, 283-298 (1975) · Zbl 0304.90058
[22] Sidney, J. B.; Steiner, G., Optimal sequencing by modular decomposition, (Working Paper 85-9 (1985), University of Ottawa: University of Ottawa Ottawa, Ont) · Zbl 0609.90068
[23] Spinrad, J., Two dimensional partial orders, (Ph.D. Thesis (1982), Princeton University: Princeton University Princeton, NJ)
[24] Spinrad, J., On comparability and permutation graphs, SIAM J. Comput., 14, 658-670 (1985) · Zbl 0568.68051
[25] Spinrad, J.; Valdes, J., Recognition and isomorphism of two dimensional partial orders, (Proceedings of the 10th Colloquium on Automata, Languages, and Programming. Proceedings of the 10th Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 154 (1983), Springer: Springer Berlin), 676-686
[26] Steiner, G., Machine scheduling with precedence constraints, (Ph.D. Thesis (1982), Department of Combinatorics and Optimization, University of Waterloo: Department of Combinatorics and Optimization, University of Waterloo Waterloo, Ont) · Zbl 0474.90048
[27] Steiner, G., On finding the jump number of a partial order by substitution decomposition, Order, 2, 9-23 (1985) · Zbl 0624.06002
[28] Sumner, D. P., Graphs undecomposable with respect to the X-join, Discrete Math., 6, 281-298 (1973) · Zbl 0279.05125
[29] Tarjan, R. E., Efficiency of a good but not linear set union algorithm, J. ACM, 22, 215-225 (1975) · Zbl 0307.68029
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.