{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:49:38Z","timestamp":1740098978419,"version":"3.37.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_26","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T02:06:22Z","timestamp":1509501982000},"page":"344-357","source":"Crossref","is-referenced-by-count":6,"title":["Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity"],"prefix":"10.1007","author":[{"given":"Du\u0161an","family":"Knop","sequence":"first","affiliation":[]},{"given":"Martin","family":"Kouteck\u00fd","sequence":"additional","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Toufar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-319-48749-6","volume-title":"COCOA","author":"SR Alves","year":"2016","unstructured":"Alves, S.R., Dabrowski, K.K., Faria, L., Klein, S., Sau, I., dos Santos Souza, U.: On the (parameterized) complexity of recognizing well-covered (r, 1) graphs. In: Chan, T.H.H., Li, M., Wang, L. (eds.) COCOA. LNCS, pp. 423\u2013437. Springer, Heidelberg (2016). doi: 10.1007\/978-3-319-48749-6"},{"issue":"2","key":"26_CR2","doi-asserted-by":"crossref","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 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 1\u201314. Springer, Heidelberg (2006). doi: 10.1007\/11917496_1"},{"key":"26_CR4","doi-asserted-by":"crossref","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. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"2","key":"26_CR5","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 optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125\u2013150 (2000). http:\/\/dx.doi.org\/10.1007\/s002249910009","journal-title":"Theor. Comput. Syst."},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-55121-2_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Courcelle","year":"1992","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 13\u201324. Springer, Heidelberg (1992). doi: 10.1007\/3-540-55121-2_2"},{"key":"26_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-21275-3"},{"key":"26_CR8","unstructured":"Dvo\u0159\u00e1k, P., Knop, D., Toufar, T.: Target Set Selection in Dense Graph Classes. CoRR 1610.07530 (October 2016)"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, P., Knop, D., Masa\u0159\u00edk, T.: Anti-path cover on sparse graph classes. In: Bouda, J., Hol\u00edk, L., Kofro\u0148, J., Strej\u010dek, J., Rambousek, A. (eds.) Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Tel\u010d, Czech Republic, 21st\u201323rd October 2016. Electronic Proceedings in Theoretical Computer Science, vol. 233, pp. 82\u201386. Open Publishing Association (2016)","DOI":"10.4204\/EPTCS.233.8"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-42634-1_6","volume-title":"Computing and Combinatorics","author":"J Fiala","year":"2016","unstructured":"Fiala, J., Gaven\u010diak, T., Knop, D., Kouteck\u00fd, M., Kratochv\u00edl, J.: Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems. In: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 67\u201378. Springer, Cham (2016). doi: 10.1007\/978-3-319-42634-1_6"},{"key":"26_CR11","unstructured":"Freuder, E.C.: Complexity of K-tree structured constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence, vol. 1, pp. 49. AAAI 1990, AAAI Press (1990). http:\/\/dl.acm.org\/citation.cfm?id=1865499.1865500"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1\u20133), 3\u201331 (2004). http:\/\/dx.doi.org\/10.1016\/j.apal.2004.01.007","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"26_CR13","unstructured":"Ganian, R.: Using neighborhood diversity to solve hard problems. CoRR abs\/1201.3091 (2012). http:\/\/arxiv.org\/abs\/1201.3091"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-45278-9_15","volume-title":"Combinatorial Algorithms","author":"R Ganian","year":"2013","unstructured":"Ganian, R., Obdr\u017e\u00e1lek, J.: Expanding the expressive power of monadic second-order logic on restricted graph classes. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 164\u2013177. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-45278-9_15"},{"key":"26_CR15","unstructured":"Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theor. Comput. Sci. 566, 39\u201349 (2015). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397514009463"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures with bounded treewidth. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 165\u2013174 (2007)","DOI":"10.1145\/1265530.1265554"},{"key":"26_CR17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/conm\/558\/11051","volume":"558","author":"M Grohe","year":"2011","unstructured":"Grohe, M., Kreutzer, S.: Methods algorithmic meta theorems. Model Theor. Methods Finite Comb. 558, 181\u2013206 (2011)","journal-title":"Model Theor. Methods Finite Comb."},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). doi: 10.1007\/BFb0045375"},{"issue":"4","key":"26_CR19","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","volume":"8","author":"J Kneis","year":"2011","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Courcelle\u2019s theorem - a game-theoretic approach. Discret. Optim. 8(4), 568\u2013594 (2011)","journal-title":"Discret. Optim."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Knop, D., Kouteck\u1ef3, M., Masa\u0159\u00edk, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: Treewidth and neighborhood diversity. arXiv preprint. arXiv:1703.00544 (2017)","DOI":"10.1007\/978-3-319-68705-6_26"},{"issue":"2","key":"26_CR21","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"PG Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302\u2013332 (2000). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000000917136","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR22","unstructured":"Kolman, P., Kouteck\u00fd, M., Tiwary, H.R.: Extension complexity, MSO logic, and treewidth (v3) (12 July 2016). http:\/\/arxiv.org\/abs\/1507.04907 , short version presented at SWAT 2016"},{"key":"26_CR23","unstructured":"Kolman, P., Lidick\u00fd, B., Sereni, J.S.: On Fair Edge Deletion Problems (2009)"},{"issue":"1","key":"26_CR24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012). http:\/\/dx.doi.org\/10.1007\/s00453-011-9554-x","journal-title":"Algorithmica"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Lampis, M.: Model checking lower bounds for simple graphs. Log. Methods Comput. Sci. 10(1) (2014). http:\/\/dx.doi.org\/10.2168\/LMCS-10(1:18)2014","DOI":"10.2168\/LMCS-10(1:18)2014"},{"key":"26_CR26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.cosrev.2014.08.001","volume":"13\u201314","author":"A Langer","year":"2014","unstructured":"Langer, A., Reidl, F., Rossmanith, P., Sikdar, S.: Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev. 13\u201314, 39\u201374 (2014)","journal-title":"Comput. Sci. Rev."},{"key":"26_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer-Verlag, Berlin (2004). doi: 10.1007\/978-3-662-07003-1"},{"key":"26_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/978-3-319-55911-7_45","volume-title":"Theory and Applications of Models of Computation","author":"T Masa\u0159\u00edk","year":"2017","unstructured":"Masa\u0159\u00edk, T., Toufar, T.: Parameterized complexity of fair deletion problems. In: Gopal, T.V., J\u00e4ger, G., Steila, S. (eds.) TAMC 2017. LNCS, vol. 10185, pp. 628\u2013642. Springer, Heidelberg (2017). doi: 10.1007\/978-3-319-55911-7_45"},{"key":"26_CR29","volume-title":"Invitation to Discrete Mathematics","author":"J Matou\u0161ek","year":"2009","unstructured":"Matou\u0161ek, J., Ne\u0161et\u0159il, J.: Invitation to Discrete Mathematics, 2nd edn. Oxford University Press, Oxford (2009)","edition":"2"},{"key":"26_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-22993-0_47","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M Pilipczuk","year":"2011","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 520\u2013531. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22993-0_47"},{"issue":"2","key":"26_CR31","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1877714.1877718","volume":"12","author":"S Szeider","year":"2011","unstructured":"Szeider, S.: Monadic second order logic on graphs with local cardinality constraints. ACM Trans. Comput. Log. 12(2), 12 (2011). http:\/\/doi.acm.org\/10.1145\/1877714.1877718","journal-title":"ACM Trans. Comput. Log."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T08:11:47Z","timestamp":1570263107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}