×

zbMATH — the first resource for mathematics

Modular decomposition and transitive orientation. (English) Zbl 0933.05146
A module of a graph \(G\) is a set \(X\) of vertices such that, for every \(x\in V(G)-X\), either \(x\) is adjacent to every element of \(X\) or \(x\) is adjacent to no vertex in \(X\). The modular decomposition of \(G\) is an \(O(n)\)-space representation of the modules of \(G\). The authors introduce linear time algorithms to construct the modular decomposition of a graph and a transitive orientation of a comparability graph. Note that a linear time algorithm for the modular decompositions of both directed and undirected graphs was suggested by A. Cournier and M. Habib [Lect. Notes Comput. Sci. 657, 212-224 (1993)].
Reviewer: G.Gutin (Odense)

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Booth, S.; Lueker, S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[2] Buer, B.; Möhring, R.H., A fast algorithm for the decomposition of graphs and posets, Math. oper. res., 8, 170-184, (1983) · Zbl 0517.05057
[3] Chein, M.; Habib, M.; Maurer, M.C., Partitive hypergraphs, Discrete math., 37, 35-50, (1981) · Zbl 0478.05071
[4] Colbourn, C.J., On testing isomorphism of permutation graphs, Networks, 11, 13-21, (1981) · Zbl 0459.68031
[5] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., ()
[6] Corneil, D.G.; Lerchs, H.; Burlingham, L.S., Complement reducible graphs, Discrete appl. math., 3, 163-174, (1981) · Zbl 0463.05057
[7] Corneil, D.G.; Perl, Y.; Stewart, L.K., A linear recognition algorithm for cographs, SIAM J. comput., 3, 926-934, (1985) · Zbl 0575.68065
[8] Cournier, A.; Habib, M., An efficient algorithm to recognize prime undirected graphs, () · Zbl 0925.05051
[9] Cournier, A.; Habib, M., A new linear algorithm for modular decomposition, (), 68-82 · Zbl 0938.05502
[10] Duschnik, B.; Miller, E.W., Partially ordered sets, Amer. J. math., 63, 600-610, (1941) · Zbl 0025.31002
[11] Ehrenfeucht, A.; Gabow, H.N.; McConnell, R.M.; Sullivan, S.J., An O(n2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs, J. algorithms, 16, 283-294, (1994) · Zbl 0797.68079
[12] Ehrenfeucht, A.; Rozenberg, G., Primitivity is hereditary for 2-structures, Theoret. comput. sci., 70, 343-358, (1990) · Zbl 0701.05053
[13] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part 1: clans, basic subclasses, and morphisms, Theoret. comput. sci., 70, 277-303, (1990) · Zbl 0701.05051
[14] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part 2: representations through labeled tree families, Theoret. comput. sci., 70, 305-342, (1990) · Zbl 0701.05052
[15] Gabow, H.N.; Tarjan, R.E., A linear-time algorithm for a special case of disjoint set union, J. comput. system sci., 30, 209-221, (1985) · Zbl 0572.68058
[16] Gallai, T., Transitiv orientierbare graphen, Acta math. acad. sci. hungar., 18, 25-66, (1967) · Zbl 0153.26002
[17] Golumbic, M.C., The complexity of comparability graph recognition and coloring, J. combin. theory ser. B, 22, 68-90, (1977) · Zbl 0365.05025
[18] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[19] Gouilà-Houri, A., Caracterisation des graphes non orientès dont on peut orienter LES arrêtes de manière à obtenir le graphe d’une relation d’ordre, C. R. acad. sci. Paris, 254, 1370-1371, (1962) · Zbl 0105.35503
[20] Habib, M.; Maurer, M.C., On the X-join decomposition for undirected graphs, Discrete appl. math., 1, 201-207, (1979) · Zbl 0439.05041
[21] W. Hsu, T. Ma, Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs, manuscript. · Zbl 0918.68047
[22] McConnell, R.M., An O(n2) incremental algorithm for modular decomposition of graphs and 2-structures, Algorithmica, 14, 229-248, (1995) · Zbl 0827.05056
[23] McConnell, R.M.; Spinrad, J.P., Linear-time modular decomposition and efficient transitive orientation of comparability graphs, (), 536-545 · Zbl 0867.05068
[24] Möhring, R.H., Algorithmic aspects of comparability graphs and interval graphs, (), 41-101
[25] 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/6)
[26] Muller, J.H.; Spinrad, J., Incremental modular decomposition, J. ACM, 36, 1-19, (1989) · Zbl 0671.68030
[27] Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Canad. J. math., 23, 160-175, (1971) · Zbl 0204.24604
[28] Rotem, D.; Urrutia, J., Circular permutation graphs, Networks, 12, 429-437, (1982) · Zbl 0508.05060
[29] Spinrad, J.; Valdes, J., Recognition and isomorphism of two-dimensional partial orders, (), 676-686
[30] Spinrad, J.P., On comparability and permutation graphs, SIAM J. comput., 14, 658-670, (1985) · Zbl 0568.68051
[31] Spinrad, J.P., P4 trees and substitution decomposition, Discrete appl. math., 39, 263-291, (1992) · Zbl 0758.68036
[32] Sritharan, R., A linear time algorithm to recognize circular permutation graphs, Networks, 27, 171-174, (1996) · Zbl 0853.05073
[33] Steiner, G., Machine scheduling with precedence constraints, () · Zbl 0474.90048
[34] Valdes, J.; Tarjan, R.E.; Lawler, E.L., The recognition of series-parallel digraphs, SIAM J. comput., 11, 299-313, (1982) · Zbl 0478.68065
[35] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. algebraic discrete meth., 3, 303-322, (1982)
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.