{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:58Z","timestamp":1771036378557,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705741","type":"print"},{"value":"9783540705758","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_52","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"634-645","source":"Crossref","is-referenced-by-count":68,"title":["Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations"],"prefix":"10.1007","author":[{"given":"Marc","family":"Tedder","sequence":"first","affiliation":[]},{"given":"Derek","family":"Corneil","sequence":"additional","affiliation":[]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.46298\/dmtcs.298","volume":"5","author":"C. Capelle","year":"2002","unstructured":"Capelle, C., Habib, M., de Montgolfier, F.: Graph decompositions and factorizing permutations. Discrete Mathematics and Theoretical Computer Science\u00a05, 55\u201370 (2002)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"52_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","volume":"37","author":"M. Chein","year":"1981","unstructured":"Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discrete Mathematics\u00a037, 35\u201350 (1981)","journal-title":"Discrete Mathematics"},{"key":"52_CR3","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal of Computing\u00a014, 926\u2013934 (1985)","journal-title":"SIAM Journal of Computing"},{"key":"52_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in Algebra and Programming - CAAP \u201994","author":"A. Cournier","year":"1994","unstructured":"Cournier, A., Habib, M.: A new linear algorithm of modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol.\u00a0787, pp. 68\u201384. Springer, Heidelberg (1994)"},{"key":"52_CR5","unstructured":"Cowan, D.D., James, L.O., Stanton, R.G.: Graph decomposition for undirected graphs. In: 3rd S-E Conference on Combinatorics, Graph Theory and Computing, Utilitas Math., pp. 281\u2013290 (1972)"},{"key":"52_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(93)E0138-O","volume":"57","author":"E. Dahlhaus","year":"1995","unstructured":"Dahlhaus, E.: Efficient parallel algorithms for cographs and distance hereditary graphs. Discrete Applied Mathematics\u00a057, 29\u201354 (1995)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"52_CR7","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1006\/jagm.2001.1185","volume":"41","author":"E. Dahlhaus","year":"2001","unstructured":"Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical algorithm for sequential modular decomposition algorithm. Journal of Algorithms\u00a041(2), 360\u2013387 (2001)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"52_CR8","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/S0895480198339237","volume":"18","author":"C.M.H. de Figueiredo","year":"2005","unstructured":"de Figueiredo, C.M.H., Maffray, F.: Optimizing bull-free perfect graphs. SIAM J. Discret. Math.\u00a018(2), 226\u2013240 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1006\/jagm.1994.1013","volume":"16","author":"A. Ehrenfeucht","year":"1994","unstructured":"Ehrenfeucht, A., Gabow, H.N., McConnell, R.M., Sullivan, S.L.: An O(n\n                    2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Journal of Algorithms\u00a016, 283\u2013294 (1994)","journal-title":"Journal of Algorithms"},{"key":"52_CR10","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/800061.808753","volume-title":"STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing","author":"H.N. Gabow","year":"1983","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 246\u2013251. ACM Press, New York (1983)"},{"issue":"8","key":"52_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1186\/gb-2004-5-8-r57","volume":"5","author":"J. Gagneur","year":"2004","unstructured":"Gagneur, J., Krause, R., Bouwmeester, T., Casari, G.: Modular decomposition of protein-protein interaction networks. Genome Biology\u00a05(8), R57 (2004)","journal-title":"Genome Biology"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hungar.\u00a018, 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"52_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-27810-8_17","volume-title":"Algorithm Theory - SWAT 2004","author":"M. Habib","year":"2004","unstructured":"Habib, M., de Montgolfier, F., Paul, C.: A simple linear-time modular decomposition algorithm for graphs, using order extension. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 187\u2013198. Springer, Heidelberg (2004)"},{"key":"52_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0166-218X(79)90043-X","volume":"1","author":"M. Habib","year":"1979","unstructured":"Habib, M., Maurer, M.C.: On the x-join decomposition of undirected graphs. Discrete Applied Mathematics\u00a01, 201\u2013207 (1979)","journal-title":"Discrete Applied Mathematics"},{"key":"52_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BFb0028546","volume-title":"STACS 98","author":"M. Habib","year":"1998","unstructured":"Habib, M., Paul, C., Viennot, L.: A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 25\u201338. Springer, Heidelberg (1998)"},{"key":"52_CR16","unstructured":"McConnell, R.M., Spinrad, J.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 536\u2013545 (1994)"},{"key":"52_CR17","first-page":"45","volume":"4","author":"R.M. McConnell","year":"2000","unstructured":"McConnell, R.M., Spinrad, J.: Ordered vertex partitioning. Discrete Mathematics and Theoretical Computer Science\u00a04, 45\u201360 (2000)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"52_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-94-009-5315-4_2","volume-title":"Graphs and Orders","author":"R.H. M\u00f6hring","year":"1985","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Rival, I. (ed.) Graphs and Orders, pp. 41\u2013101. D. Reidel, Boston (1985)"},{"key":"52_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02022041","volume":"4","author":"R.H. M\u00f6hring","year":"1985","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research\u00a04, 195\u2013225 (1985)","journal-title":"Annals of Operations Research"},{"key":"52_CR20","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with cominatorial optimization. Annals of Discrete Mathematics\u00a019, 257\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"52_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J.H. Muller","year":"1989","unstructured":"Muller, J.H., Spinrad, J.: Incremental modular decomposition. Journal of the ACM\u00a036(1), 1\u201319 (1989)","journal-title":"Journal of the ACM"},{"key":"52_CR22","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/11618058_31","volume-title":"Graph Drawing","author":"C. Papadopoulos","year":"2006","unstructured":"Papadopoulos, C., Voglis, C.: Drawing graphs using modular decomposition. In: Healy, P., Nikolov, N.S. (eds.) Graph Drawing, Limerick, Ireland, September 12-14, 2005, pp. 343\u2013354. Springer, Heidelberg (2006)"},{"key":"52_CR23","doi-asserted-by":"publisher","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"Pnueli, A., Even, S., Lempel, A.: Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math.\u00a023, 160\u2013175 (1971)","journal-title":"Canad. J. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:30:08Z","timestamp":1714620608000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}