{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:48:24Z","timestamp":1760298504612},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,4,14]],"date-time":"2012-04-14T00:00:00Z","timestamp":1334361600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9399-y","type":"journal-article","created":{"date-parts":[[2012,4,12]],"date-time":"2012-04-12T21:14:39Z","timestamp":1334265279000},"page":"599-644","source":"Crossref","is-referenced-by-count":22,"title":["The Rank-Width of Edge-Coloured Graphs"],"prefix":"10.1007","volume":"52","author":[{"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,4,14]]},"reference":[{"key":"9399_CR1","first-page":"159","volume-title":"WG, LNCS","author":"I. Adler","year":"2010","unstructured":"Adler, I., Bui-Xuan, B., Rabinovich, Y., Renault, G., Telle, J.A., Vatshelle, M.: On the Boolean-width of a graph: structure and applications. In: Thilikos, D.M. (ed.) WG, LNCS, vol. 6410, pp. 159\u2013170. Springer, Berlin (2010)"},{"key":"9399_CR2","first-page":"52","volume-title":"ISAAC, LNCS","author":"B. Bui-Xuan","year":"2007","unstructured":"Bui-Xuan, B., Habib, M., Limouzy, V., de Montgolfier, F.: Unifying two graph decompositions with modular decomposition. In: Tokuyama, T. (ed.) ISAAC, LNCS, vol. 4835, pp. 52\u201364. Springer, Berlin (2007)"},{"issue":"7","key":"9399_CR3","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1016\/j.dam.2009.09.009","volume":"158","author":"B. Bui-Xuan","year":"2010","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: H-join decomposable graphs and algorithms with runtime single exponential in rank-width. Discrete Appl. Math. 158(7), 809\u2013819 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9399_CR4","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0608028","volume":"8","author":"A. Bouchet","year":"1987","unstructured":"Bouchet, A.: Digraph decompositions and Eulerian systems. SIAM J. Algebr. Discrete Methods 8(3), 323\u2013337 (1987)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"9399_CR5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1006\/jctb.1994.1008","volume":"60","author":"A. Bouchet","year":"1994","unstructured":"Bouchet, A.: Circle graph obstructions. J. Comb. Theory, Ser. B 60(1), 107\u2013144 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"6","key":"9399_CR6","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1016\/j.ic.2005.11.006","volume":"204","author":"A. Blumensath","year":"2006","unstructured":"Blumensath, A., Courcelle, B.: Recognisability, hypergraph operations and logical types. Inf. Comput. 204(6), 853\u2013919 (2006)","journal-title":"Inf. Comput."},{"key":"9399_CR7","first-page":"126","volume-title":"LATIN, LNCS","author":"D.G. Corneil","year":"2000","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J., Reed, B.A., Rotics, U.: Polynomial time recognition of clique-width\u22643 graphs. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN, LNCS, vol. 1776, pp. 126\u2013134. Springer, Berlin (2000)"},{"issue":"2","key":"9399_CR8","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"9399_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(95)00145-X","volume":"163","author":"B. Courcelle","year":"1996","unstructured":"Courcelle, B.: Basic notions of universal algebra for language theory and graph grammars. Theor. Comput. Sci. 163(1\u20132) 1\u201354 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9399_CR10","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jal.2005.08.004","volume":"4","author":"B. Courcelle","year":"2006","unstructured":"Courcelle, B.: The monadic second-order logic of graphs XV: on a conjecture by D. Seese. J. Appl. Log. 4(6), 79\u2013114 (2006)","journal-title":"J. Appl. Log."},{"key":"9399_CR11","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach","author":"B. Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach. Encyclopedia of Mathematics and Its Applications, vol.\u00a0138. Cambridge University Press, Cambridge (2012)"},{"key":"9399_CR12","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: On the model-checking of monadic second-order formulas with edge set quantifications. Discrete Appl. Math. (2012, to appear). doi: 10.1016\/j.dam.2010.12.017","DOI":"10.1016\/j.dam.2010.12.017"},{"issue":"4","key":"9399_CR13","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/j.dam.2008.08.026","volume":"157","author":"B. Courcelle","year":"2009","unstructured":"Courcelle, B., Kant\u00e9, M.M.: Graph operations characterising rank-width. Discrete Appl. Math. 157(4), 627\u2013640 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9399_CR14","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1017\/S0960129501003565","volume":"12","author":"B. Courcelle","year":"2002","unstructured":"Courcelle, B., Makowsky, J.A.: Fusion in relational structures and the verification of monadic second-order properties. Math. Struct. Comput. Sci. 12, 203\u2013235 (2002)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"2","key":"9399_CR15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimisation problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"9399_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9399_CR17","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B. Courcelle","year":"2007","unstructured":"Courcelle, B., Oum, S.: Vertex-minors, monadic second-order logic and a conjecture by Seese. J.\u00a0Comb. Theory, Ser. B 97(1), 91\u2013126 (2007)","journal-title":"J.\u00a0Comb. Theory, Ser. B"},{"issue":"2","key":"9399_CR18","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"W.H. Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebr. Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9399_CR19","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"key":"9399_CR20","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)"},{"issue":"2","key":"9399_CR21","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"9399_CR22","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fisher","year":"2008","unstructured":"Fisher, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Appl. Math. 156(4), 511\u2013529 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9399_CR23","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1007\/s00224-009-9241-3","volume":"46","author":"U. Flarup","year":"2010","unstructured":"Flarup, U., Lyaudet, L.: On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth\/cliquewidth. Theory Comput. Syst. 46(4), 761\u2013791 (2010)","journal-title":"Theory Comput. Syst."},{"key":"9399_CR24","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-94-009-1606-7_3","volume-title":"Discrete Analysis and Operations Research","author":"D.G. Fon-Der-Flaass","year":"1996","unstructured":"Fon-Der-Flaass, D.G.: Local complementation of simple and directed graphs. In: Discrete Analysis and Operations Research, vol.\u00a01, pp.\u00a015\u201334 (1996)"},{"key":"9399_CR25","doi-asserted-by":"crossref","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Obdrz\u00e1lek, J.: Unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width. (2012, submitted)","DOI":"10.1016\/j.ejc.2012.07.024"},{"key":"9399_CR26","first-page":"73","volume-title":"FSTTCS, LIPIcs","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Obdrz\u00e1lek, J.: Better algorithms for satisfiability problems for formulas of bounded rank-width. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS, LIPIcs, vol. 8, pp. 73\u201383. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Saarbr\u00fccken (2010)"},{"key":"9399_CR27","first-page":"185","volume-title":"IWPEC, LNCS","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdrz\u00e1lek, J., Rossmanith, P.: On digraph width measures in parameterized algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC, LNCS, vol. 5917, pp. 185\u2013197. Springer, Berlin (2009)"},{"issue":"7","key":"9399_CR28","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Appl. Math. 158(7), 851\u2013867 (2010)","journal-title":"Discrete Appl. Math."},{"key":"9399_CR29","first-page":"135","volume-title":"IPEC, LNCS","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Meister, D., Obdrz\u00e1lek, J., Rossmanith, P., Sikdar, S.: Are there any good digraph width measure? In: Raman, V., Saurabh, S. (eds.) IPEC, LNCS, vol. 6478, pp. 135\u2013146. Springer, Berlin (2010)"},{"issue":"2","key":"9399_CR30","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1006\/jctb.2001.2082","volume":"84","author":"J.F. Geelen","year":"2002","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.P.: Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B 84(2), 270\u2013290 (2002)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9399_CR31","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0095-8956(02)00046-1","volume":"88","author":"J.F. Geelen","year":"2003","unstructured":"Geelen, J.F., Gerards, A.M.H., Robertson, N., Whittle, G.P.: On the excluded minors for the matroids of branch-width k. J. Comb. Theory, Ser. B 88(2), 261\u2013265 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"6","key":"9399_CR32","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.jctb.2007.02.005","volume":"97","author":"J.F. Geelen","year":"2007","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.P.: Excluding a planar graph from GF(q)-representable matroids. J. Comb. Theory, Ser. B 97(6), 971\u2013998 (2007)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9399_CR33","doi-asserted-by":"crossref","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.P.: Towards a matroid minor structure theory. In: G. Grimmett and C. McDiarmid (eds.) Combinatorics, Complexity and Chance\u2014A Tribute to Dominic Welsh, Chap.\u00a05","DOI":"10.1093\/acprof:oso\/9780198571278.003.0005"},{"issue":"3","key":"9399_CR34","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2005.08.005","volume":"96","author":"P. Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Branch-width parse trees, and monadic second-order logic for matroids. J. Comb. Theory, Ser. B 96(3), 325\u2013351 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"9399_CR35","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1017\/S0963548305007297","volume":"15","author":"P. Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: The tutte polynomial for matroids of bounded branch-width. Comb. Probab. Comput. 15(3), 397\u2013409 (2006)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"9399_CR36","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"9399_CR37","doi-asserted-by":"crossref","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M. Kaminski","year":"2009","unstructured":"Kaminski, M., Lozin, V.V., Recent, M.M.: Developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9399_CR38","unstructured":"Kant\u00e9, M.M.: The rank-width of directed graphs. arXiv:0709.1433 (2008)"},{"key":"9399_CR39","author":"M.M. Kant\u00e9","year":"2012","unstructured":"Kant\u00e9, M.M.: Well-quasi-ordering of matrices under Schur complement and applications to directed graphs. Eur. J. Comb. (2012, accepted). doi: 10.1016\/j.ejc.2012.03.034 . arXiv:1102.2134","journal-title":"Eur. J. Comb."},{"key":"9399_CR40","first-page":"214","volume-title":"WG, LNCS","author":"M.M. Kant\u00e9","year":"2009","unstructured":"Kant\u00e9, M.M., Rao, M.: Directed rank-width and displit decomposition. In: Paul, C., Habib, M. (eds.) WG, LNCS, vol. 5911, pp. 214\u2013225. Springer, Berlin (2009)"},{"key":"9399_CR41","unstructured":"Kant\u00e9, M.M., Rao, M.: Bipartitive decomposition of 2-structures. Manuscript (2010)"},{"key":"9399_CR42","volume-title":"Schaum\u2019s Outline of Theory and Problems of Linear Algebra","author":"S. Lipschutz","year":"1991","unstructured":"Lipschutz, S.: Schaum\u2019s Outline of Theory and Problems of Linear Algebra, 2nd edn. McGraw-Hill, New York (1991)","edition":"2"},{"key":"9399_CR43","series-title":"Encyclopedia of Mathematics and its Applications","volume-title":"Finite Fields","author":"R. Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Applications, vol.\u00a020, 2nd edn. Cambridge University Press, Cambridge (1997)","edition":"2"},{"issue":"5","key":"9399_CR44","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1016\/j.jctb.2007.04.001","volume":"97","author":"V.V. Lozin","year":"2007","unstructured":"Lozin, V.V., Rautenbach, D.: The relative clique-width of a graph. J. Comb. Theory, Ser. B 97(5), 846\u2013858 (2007)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"9399_CR45","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S. Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"9399_CR46","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S. Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9399_CR47","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1137\/050629616","volume":"22","author":"S. Oum","year":"2008","unstructured":"Oum, S.: Rank-width and well-quasi-ordering. SIAM J. Discrete Math. 22(2), 666\u2013682 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9399_CR48","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II: algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9399_CR49","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors I to XX"},{"issue":"10","key":"9399_CR50","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.dam.2011.02.005","volume":"159","author":"Y. Strozecki","year":"2011","unstructured":"Strozecki, Y.: Monadic second-order model-checking on decomposable matroids. Discrete Appl. Math. 159(10), 1022\u20131039 (2011)","journal-title":"Discrete Appl. Math."},{"key":"9399_CR51","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency, vol.\u00a0B. Springer, Berlin (2003)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9399-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9399-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9399-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,27]],"date-time":"2019-06-27T02:28:31Z","timestamp":1561602511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9399-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,14]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9399"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9399-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,14]]}}}