{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:13:41Z","timestamp":1775837621935,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325885","type":"print"},{"value":"9783642325892","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_38","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T04:44:32Z","timestamp":1343796272000},"page":"419-430","source":"Crossref","is-referenced-by-count":17,"title":["When Trees Grow Low: Shrubs and Fast MSO1"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Obdr\u017e\u00e1lek","sequence":"additional","affiliation":[]},{"given":"Patrice","family":"Ossona de Mendez","sequence":"additional","affiliation":[]},{"given":"Reshma","family":"Ramadurai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/3-540-59071-4_56","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Rankings of Graphs. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol.\u00a0903, pp. 292\u2013304. Springer, Heidelberg (1995)"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput.\u00a085, 12\u201375 (1990)","journal-title":"Inform. and Comput."},{"issue":"2","key":"38_CR3","doi-asserted-by":"publisher","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 optimization problems on graphs of bounded clique-width. Theory Comput. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1-3","key":"38_CR4","doi-asserted-by":"publisher","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.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"38_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/3-540-57785-8_187","volume-title":"STACS 94","author":"J. Deogun","year":"1994","unstructured":"Deogun, J., Kloks, T., Kratsch, D., Muller, H.: On Vertex Ranking for Permutation and Other Graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 747\u2013758. Springer, Heidelberg (1994)"},{"key":"38_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W. Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"issue":"1-3","key":"38_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M. Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic\u00a0130(1-3), 3\u201331 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"38_CR8","unstructured":"Gajarsk\u00fd, J.: Efficient solvability of graph MSO properties. Master\u2019s thesis, Masaryk University, Brno (2012)"},{"key":"38_CR9","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, P.: Deciding graph MSO properties: Has it all been told already (submitted, 2012)"},{"key":"38_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-642-28050-4_21","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2012","unstructured":"Ganian, R.: Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 259\u2013271. Springer, Heidelberg (2012)"},{"key":"38_CR11","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J.: Clique-width: When hard does not mean impossible. In: STACS 2011. LIPIcs, vol.\u00a09, pp. 404\u2013415. Dagstuhl Publishing (2011)"},{"issue":"1-3","key":"38_CR12","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0304-3975(02)00725-9","volume":"299","author":"M.U. Gerber","year":"2003","unstructured":"Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theoret. Comput. Sci.\u00a0299(1-3), 719\u2013734 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1006\/aama.1996.0519","volume":"18","author":"V. Giakoumakis","year":"1997","unstructured":"Giakoumakis, V., Vanherpe, J.-M.: Bi-complement reducible graphs. Adv. Appl. Math.\u00a018, 389\u2013402 (1997)","journal-title":"Adv. Appl. Math."},{"key":"38_CR14","first-page":"1","volume":"2011","author":"L.-J. Hung","year":"2011","unstructured":"Hung, L.-J., Kloks, T.: k-cographs are Kruskalian. Chic. J. Theoret. Comput. Sci.\u00a02011, 1\u201311 (2011)","journal-title":"Chic. J. Theoret. Comput. Sci."},{"key":"38_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-642-15775-2_47","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Lampis","year":"2010","unstructured":"Lampis, M.: Algorithmic Meta-theorems for Restrictions of Treewidth. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 549\u2013560. Springer, Heidelberg (2010)"},{"issue":"6","key":"38_CR16","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin.\u00a027(6), 1024\u20131041 (2006)","journal-title":"European J. Combin."},{"issue":"3","key":"38_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. European J. Combin.\u00a029(3), 760\u2013776 (2008)","journal-title":"European J. Combin."},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms) Algorithms and Combinatorics, vol.\u00a028, p. 465. Springer (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"38_CR19","first-page":"58","volume-title":"Logic, Methodology and Philosophy of Sciences","author":"M.O. Rabin","year":"1964","unstructured":"Rabin, M.O.: A simple method for undecidability proofs and some applications. In: Bar-Hillel, Y. (ed.) Logic, Methodology and Philosophy of Sciences, vol.\u00a01, pp. 58\u201368. North-Holland, Amsterdam (1964)"},{"key":"38_CR20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"P. Schaffer","year":"1989","unstructured":"Schaffer, P.: Optimal node ranking of trees in linear time. Inform. Process. Lett.\u00a033, 91\u201396 (1989\/1990)","journal-title":"Inform. Process. Lett."},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Appl. Math.\u00a054, 251\u2013266 (1994)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:08:07Z","timestamp":1620115687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}