{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:25Z","timestamp":1725582265825},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_49","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T02:35:17Z","timestamp":1303871717000},"page":"505-516","source":"Crossref","is-referenced-by-count":4,"title":["Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Langer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"49_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"49_CR2","volume-title":"Winning Ways for Your Mathematical Plays","author":"E.R. Berlekamp","year":"1982","unstructured":"Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays. A.K. Peters, Wellesley (1982)"},{"key":"49_CR3","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 theory of Graphs I: Recognisable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"issue":"1","key":"49_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: Monadic second-order definable graph transductions: A survey. Theor. Comput. Sci.\u00a0126(1), 53\u201375 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"49_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-74839-7_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"2007","unstructured":"Courcelle, B., Kant\u00e9, M.M.: Graph operations characterizing rank-width and balanced graph expressions. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 66\u201375. Springer, Heidelberg (2007)"},{"key":"49_CR6","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, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1-2","key":"49_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-2","key":"49_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci.\u00a0109(1-2), 49\u201382 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"49_CR9","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1999)"},{"key":"49_CR10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"S. Feferman","year":"1959","unstructured":"Feferman, S., Vaught, R.: The first order properties of algebraic systems. Fund. Math.\u00a047, 57\u2013103 (1959)","journal-title":"Fund. Math."},{"issue":"7","key":"49_CR11","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011ben\u00fd, P.: On parse trees and Myhill\u2013Nerode\u2013type tools for handling graphs of bounded rank-width. Disc. App. Math.\u00a0158(7), 851\u2013867 (2010)","journal-title":"Disc. App. Math."},{"key":"49_CR12","doi-asserted-by":"crossref","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J.: Unified approach to polynomial algorithms on graphs of\u00a0bounded (bi-)rank-width (2009) (submitted)","DOI":"10.1007\/978-3-642-10217-2_27"},{"key":"49_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-68804-8_3","volume-title":"Finite Model Theory and Its Applications","author":"E. Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E.: Finite model theory and descriptive complexity. In: Finite Model Theory and Its Applications, pp. 125\u2013230. Springer, Heidelberg (2007)"},{"issue":"4","key":"49_CR14","doi-asserted-by":"publisher","first-page":"481","DOI":"10.2307\/2273287","volume":"44","author":"Y. Gurevich","year":"1979","unstructured":"Gurevich, Y.: Modest Theory of Short Chains. I. J. Symb. Log.\u00a044(4), 481\u2013490 (1979)","journal-title":"J. Symb. Log."},{"key":"49_CR15","first-page":"479","volume-title":"Model-Theoretic Logics","author":"Y. Gurevich","year":"1985","unstructured":"Gurevich, Y.: Monadic second-order theories. In: Jon Barwise, S.F. (ed.) Model-Theoretic Logics, pp. 479\u2013506. Springer, Heidelberg (1985)"},{"key":"49_CR16","volume-title":"Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic","author":"J. Hintikka","year":"1973","unstructured":"Hintikka, J.: Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic. Clarendon Press, Oxford (1973)"},{"key":"49_CR17","doi-asserted-by":"publisher","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-decomposition and rank-decomposition. SIAM Journal on Computing\u00a038, 1012\u20131032 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"49_CR18","unstructured":"Kante, M.M.: The rankwidth of directed graphs (2007) (preprint), \n                      \n                        http:\/\/arxiv.org\/abs\/0709.1433"},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Courcelle\u2019s Theorem \u2013 a game-theoretic approach (2010) (submitted)","DOI":"10.1016\/j.disopt.2011.06.001"},{"key":"49_CR20","unstructured":"Oum, S.: Graphs of Bounded Rankwidth. PhD thesis, Princeton University (2005)"},{"issue":"4","key":"49_CR21","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory Series B\u00a096(4), 514\u2013528 (2006)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"49_CR22","volume-title":"Proceedings of the 2006 IEEE Symposium on Security and Privacy","author":"L. \u00d8verlier","year":"2006","unstructured":"\u00d8verlier, L., Syverson, P.: Locating hidden servers. In: Proceedings of the 2006 IEEE Symposium on Security and Privacy. IEEE CS, Los Alamitos (May 2006)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T01:18:32Z","timestamp":1558574312000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}