{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:26:08Z","timestamp":1767245168062},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"},{"type":"electronic","value":"9783540771203"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77120-3_7","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"52-64","source":"Crossref","is-referenced-by-count":1,"title":["Unifying Two Graph Decompositions with Modular Decomposition"],"prefix":"10.1007","author":[{"given":"Binh-Minh","family":"Bui-Xuan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Limouzy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabien","family":"de Montgolfier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","series-title":"Springer Monographs in Mathematics","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2001","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer, Heidelberg (2001)"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Brandstadt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM\u00a0 (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"7_CR3","unstructured":"Bui-Xuan, B.-M., Habib, M., Limouzy, V., de Montgolfier, F.: Algorithmic aspects of a general modular decomposition theory. Technical report (to appear)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B.-M. Bui Xuan","year":"2006","unstructured":"Bui Xuan, B.-M., Habib, M., Limouzy, V., de Montgolfier, F.: Homogeneity vs. adjacency: generalising some graph decomposition algorithms. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, Springer, Heidelberg (2006)"},{"key":"7_CR5","unstructured":"Bui-Xuan, B.-M., Habib, M., Limouzy, V., de Montgolfier, F.: A new tractable decomposition. Technical report (2007), \n                    \n                      http:\/\/hal-lirmm.ccsd.cnrs.fr\/lirmm-00157502"},{"issue":"1","key":"7_CR6","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(1), 35\u201350 (1981)","journal-title":"Discrete Mathematics"},{"key":"7_CR7","unstructured":"Clarou, E.: Une hi\u00e9rarchie de for\u00e7age pour les tournois ind\u00e9composables. PhD thesis, Universit\u00e9 Claude Bernard Lyon I (1996)"},{"issue":"3","key":"7_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0166-218X(80)90038-4","volume":"2","author":"C.J. Colbourn","year":"1980","unstructured":"Colbourn, C.J., Corneil, D.G.: On deciding switching equivalence of graphs. Discrete Applied Mathematics\u00a02(3), 181\u2013184 (1980)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR9","unstructured":"Corneil, D.G.: Private communication. Dagstuhl (2007)"},{"key":"7_CR10","unstructured":"Cunningham, W.H.: A combinatorial decomposition theory. PhD thesis, University of Waterloo, Waterloo, Ontario, Canada (1973)"},{"key":"7_CR11","doi-asserted-by":"crossref","DOI":"10.1142\/4197","volume-title":"The Theory of 2-Structures- A Framework for Decomposition and Transformation of Graphs","author":"A. Ehrenfeucht","year":"1999","unstructured":"Ehrenfeucht, A., Harju, T., Rozenberg, G.: The Theory of 2-Structures- A Framework for Decomposition and Transformation of Graphs. World Scientific, Singapore (1999)"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0165-4896(91)90080-B","volume":"21","author":"M.G. Everett","year":"1991","unstructured":"Everett, M.G., Borgatti, S.P.: Role colouring a graph. Mathematical Social Sciences\u00a021, 183\u2013188 (1991)","journal-title":"Mathematical Social Sciences"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/3-540-45061-0_64","volume-title":"Automata, Languages and Programming","author":"J. Fiala","year":"2003","unstructured":"Fiala, J., Paulusma, D.: The computational complexity of the role assignment problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 817\u2013828. Springer, Heidelberg (2003)"},{"issue":"3","key":"7_CR14","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1006\/jagm.1995.1022","volume":"18","author":"H.N. Gabow","year":"1995","unstructured":"Gabow, H.N.: Centroids, representations, and submodular flows. Journal of Algorithms\u00a018(3), 586\u2013628 (1995)","journal-title":"Journal of Algorithms"},{"key":"7_CR15","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":"7_CR16","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0012-365X(85)90132-3","volume":"53","author":"M. Habib","year":"1985","unstructured":"Habib, M., Maurer, M.C.: 1-intersecting families. Discrete Mathematics\u00a053, 91\u2013101 (1985)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jctb.1996.0018","volume":"66","author":"R.B. Hayward","year":"1996","unstructured":"Hayward, R.B.: Recognizing 3-structure: A switching approach. Journal of Combinatorial Theory, Series B\u00a066(2), 247\u2013262 (1996)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1-3","key":"7_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00153-X","volume":"94","author":"A. Hertz","year":"1999","unstructured":"Hertz, A.: On perfect switching classes. Discrete Applied Mathematics\u00a094(1-3), 3\u20137 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(02)00435-8","volume":"296","author":"W.-L. Hsu","year":"2003","unstructured":"Hsu, W.-L., McConnell, R.M.: PC-trees and circular-ones arrangements. Theoretical Computer Science\u00a0296, 99\u2013116 (2003)","journal-title":"Theoretical Computer Science"},{"key":"7_CR20","series-title":"Ann. Discrete Math","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0167-5060(08)70622-8","volume-title":"Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990)","author":"J. Kratochv\u00edl","year":"1992","unstructured":"Kratochv\u00edl, J., Ne\u0161et\u0159il, J., Z\u00fdka, O.: On the computational complexity of Seidel\u2019s switching. In: Kratochv\u00edl, J., Ne\u0161et\u0159il, J. (eds.) Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990). Ann. Discrete Math, vol.\u00a051, pp. 161\u2013166. North-Holland, Amsterdam (1992)"},{"key":"7_CR21","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 combinatorial optimization. Annals of Discrete Mathematics\u00a019, 257\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"key":"7_CR22","unstructured":"de Montgolfier, F.: D\u00e9composition modulaire des graphes. Th\u00e9orie, extensions et algorithmes. PhD thesis, Universit\u00e9 Montpellier II (2003)"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"de Montgolfier, F., Rao, M.: The bi-join decomposition. In: ICGT 2005, 7th International Colloquium on Graph Theory (2005)","DOI":"10.1016\/j.endm.2005.06.039"},{"issue":"6","key":"7_CR24","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM Journal on Computing\u00a016(6), 973\u2013989 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR25","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"7_CR26","unstructured":"Seidel, J.J.: A survey of two-graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I, pp. 481\u2013511. Atti dei Convegni Lincei, No. 17. Accad. Naz. Lincei, Rome (1976)"},{"key":"7_CR27","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0378-8733(83)90025-4","volume":"5","author":"D.R. White","year":"1983","unstructured":"White, D.R., Reitz, K.P.: Graph and semigroup homomorphisms on networks of relations. Social Networks\u00a05, 193\u2013234 (1983)","journal-title":"Social Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T08:07:07Z","timestamp":1551168427000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540771180","9783540771203"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}