{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T00:31:23Z","timestamp":1773448283882,"version":"3.50.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":30,"publisher":"Springer-Verlag","isbn-type":[{"value":"354057879X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0017474","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T02:47:11Z","timestamp":1132627631000},"page":"68-84","source":"Crossref","is-referenced-by-count":83,"title":["A new linear algorithm for Modular Decomposition"],"prefix":"10.1007","author":[{"given":"Alain","family":"Cournier","sequence":"first","affiliation":[]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","first-page":"212","volume-title":"Lectures notes in Computer Science, 657","author":"A. Cournier","year":"1993","unstructured":"A. Cournier and M. Habib. An efficient algorithm to recognize prime undirected graphs. In E. W. Mayr, editor, Lectures notes in Computer Science, 657.Graph-Theoretic Concepts in Computer Science. 18th International Workshop, WG'92. Wiesbaden-Naurod, Germany, June 1992. Proceding, pages 212\u2013224. Springer-Verlag, 1993."},{"key":"5_CR2","volume-title":"Raport de recherche","author":"A. Cournier","year":"1993","unstructured":"A. Cournier and M. Habib. A new linear algorithm for modular decomposition. Raport de recherche, LIRMM, 161, Rue Ada, 34392 Montpellier Cedex 5, 1993."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","volume":"37","author":"M. Chein","year":"1981","unstructured":"M. Chein, M. Habib, and M. C. Maurer. Partitive hypergraphs. Discrete Mathematics, (37):35\u201350, 1981.","journal-title":"Discrete Mathematics"},{"key":"5_CR4","unstructured":"D. D. Cowan, L. O. James, and R. G. Stanton. Graph decomposition for undirected graphs. In R. B. Levow eds. F. Hoffman, editor, 3rd S-E Conf. Combinatorics, Graph Theory and computing, Utilitas Math, pages 281\u2013290, Winnipeg, 1972."},{"key":"5_CR5","volume-title":"PhD thesis","author":"A. Cournier","year":"1993","unstructured":"A. Cournier. Sur Quelques Algorithmes de D\u00e9composition de Graphes. PhD thesis, Universit\u00e9 Montpellier II, 161 rue Ada, 34392 Montpellier Cedex 5, France, f\u00e9vrier 1993."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D. G. Corneil","year":"1985","unstructured":"D. G. Corneil, Y. Perl, and L. K. Stewart. A linear recognition algorithm for cographs. SIAM journal of computing, (14):926\u2013934, november 1985.","journal-title":"SIAM journal of computing"},{"issue":"70","key":"5_CR7","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(90)90131-Z","volume":"3","author":"A. Ehrenfeucht","year":"1990","unstructured":"A. Ehrenfeucht and G. Rozenberg. Primitivity is hereditary for 2-structures (fundamental study). Theoretical Comp. Sci., 3(70):343\u2013358, 1990.","journal-title":"Theoretical Comp. Sci."},{"issue":"70","key":"5_CR8","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(90)90129-6","volume":"3","author":"A. Ehrenfeucht","year":"1990","unstructured":"A. Ehrenfeucht and G. Rozenberg. Theory of 2-structures, part i: clans, basic subclasses and morphisms (fundamental study). Theoretical Comp. Sci., 3(70):277\u2013303, 1990.","journal-title":"Theoretical Comp. Sci."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"T. Gallai. Transitiv orienterbare graphen. Acta Math. Acad. Sci. Hungar., (18):25\u201366, 1967. MR 36 #5026.","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"5_CR10","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New-York, 1980."},{"key":"5_CR11","volume-title":"PhD thesis","author":"M. Habib","year":"1981","unstructured":"M. Habib. Substitution des structures combinatoires, th\u00e9orie et algorithmes. PhD thesis, Universit\u00e9 Pierre et Marie Curie (Paris VI), 1981."},{"key":"5_CR12","unstructured":"M. Habib, M. Huchard, and J. Spinrad. A linear algorithm to decompose inheritance graphs into modules. Rapport de Recherche CRIM-81, to appear in Algorithmica, 1990."},{"key":"5_CR13","first-page":"198","volume":"3","author":"M. Habib","year":"1979","unstructured":"M. Habib and M. C. Maurer. On the x-join decomposition for undirected graphs. Discrete Applied Math, (3):198\u2013207, 1979.","journal-title":"Discrete Applied Math"},{"key":"5_CR14","unstructured":"P. Ille. Indecomposable relations. preprint Universit\u00e9 de Marseille, 1990."},{"key":"5_CR15","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/malq.19910371306","volume":"37","author":"P. Ille","year":"1991","unstructured":"P. Ille. L'ensemble des intervalles d'une multirelation binaire et r\u00e9flexive. Zeitschr. f. math. Logik und Grundlagen d. Math. Bd., (37):227\u2013256, 1991.","journal-title":"Zeitschr. f. math. Logik und Grundlagen d. Math. Bd."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"D. Kelly. Comparability graphs. In I. Rival, editor, Graphs and Orders, pages 3\u201340. D. Reidel Publishing Company, 1985.","DOI":"10.1007\/978-94-009-5315-4_1"},{"key":"5_CR17","first-page":"285","volume":"287","author":"M.C. Vilarem","year":"1978","unstructured":"M.C. Vilarem M. Chein, M. Habib. Hypergraphes homog\u00e8nes et ensembles de parties homog\u00e8nes d'un graphe ou d'un hypergraphe. C.R. Acad Sciences Paris, (287):285\u2013287, 1978.","journal-title":"C.R. Acad Sciences Paris"},{"key":"5_CR18","volume-title":"A practical o(n 2) algorithm for substitution decomposition","author":"R. M. McConnell","year":"1992","unstructured":"R. M. McConnell. A practical o(n 2) algorithm for substitution decomposition. Dept. of computer science, University of colorado at Boulder, Boulder, CO 80309 USA, 1992."},{"key":"5_CR19","unstructured":"C.L. McCreary, C.L. Combs, D.H. Gill, and J.V. Warren. An automated graph drawing system using graph decomposition. In Graph Drawing'93, 1993."},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02022041","volume":"6","author":"R. H. M\u00f6hring","year":"1985","unstructured":"R. H. M\u00f6hring. Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research, 6:195\u2013225, 1985.","journal-title":"Annals of Operations Research"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"R. H. M\u00f6hring. Computationaly tractable classes of ordered sets. In I. Rival, editor, Algorithms and Orders, pages 105\u2013193. Kluwer Academic Publishers, 1989. volume: 255, series C: Mathematical and Physical Sciences.","DOI":"10.1007\/978-94-009-2639-4_4"},{"key":"5_CR22","first-page":"257","volume":"19","author":"R. H. M\u00f6hring","year":"1984","unstructured":"R. H. M\u00f6hring and F. J. Radermacher. Substitution decomposition for discrete structures and connections with combinatorial optimization. Ann. Discrete math, (19):257\u2013356, 1984.","journal-title":"Ann. Discrete math"},{"key":"5_CR23","first-page":"1","volume":"1","author":"J. H. Muller","year":"1989","unstructured":"J. H. Muller and J. Spinrad. Incremental modular decomposition. Journal of the association for Computing Machinery, (1):1\u201319, January 1989.","journal-title":"Journal of the association for Computing Machinery"},{"key":"5_CR24","volume-title":"Linear-time modular decomposition and efficient transitive orientation of undirected graphs","author":"R. M. McConnell","year":"1993","unstructured":"R. M. McConnell and J. Spinrad. Linear-time modular decomposition and efficient transitive orientation of undirected graphs. Dept. of computer science, University of colorado at Boulder, Boulder, CO 80309 USA, 1993."},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1215\/S0012-7094-59-02667-5","volume":"26","author":"J. Sabidussi","year":"1959","unstructured":"J. Sabidussi. The composition of graphs. Duke Math.Journal, (26):693\u2013696, 1959.","journal-title":"Duke Math.Journal"},{"key":"5_CR26","unstructured":"L. S. Shapley. In F. Zwycky and A. Wilson, editors, New Methods of Thought and Procedure, number 26, pages 693\u2013696. New-York, 1968."},{"issue":"3","key":"5_CR27","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"J. Spinrad. On comparability and permutation graphs. SIAM J. COMPUT., 14(3):658\u2013670, August 1985.","journal-title":"SIAM J. COMPUT."},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","volume":"39","author":"J. Spinrad","year":"1992","unstructured":"J. Spinrad. P4-trees and substitution decomposition. Discrete Applied Mathematics, (39):263\u2013291, 1992.","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR29","unstructured":"J. H. Schmerl and W. T. Trotter. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. preprint, 1991."},{"key":"5_CR30","volume-title":"PhD thesis","author":"D. P. Sumner","year":"1971","unstructured":"D. P. Sumner. Indecomposable graphs. PhD thesis, University of Massachussets, Amherts, 1971."}],"container-title":["Lecture Notes in Computer Science","Trees in Algebra and Programming \u2014 CAAP'94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017474.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:38:35Z","timestamp":1607531915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354057879X"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/bfb0017474","relation":{},"subject":[]}}