{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T21:42:05Z","timestamp":1774993325639,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540738138","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73814-5_28","type":"book-chapter","created":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T05:31:44Z","timestamp":1188624704000},"page":"293-304","source":"Crossref","is-referenced-by-count":1,"title":["Easy Problems for Grid-Structured Graphs"],"prefix":"10.1007","author":[{"given":"Detlef","family":"Seese","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"28_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. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"28_CR2","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial Optimization on Graphs of bounded treewidth. The Computer Journal, special Volume on FPT, pp. 1\u201326, December 2006 (to appear)"},{"issue":"2","key":"28_CR3","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second order theory of graphs III: Tree decompositions, minors, and complexity issues. Theoret. Inform. Applic.\u00a026(2), 257\u2013286 (1992)","journal-title":"Theoret. Inform. Applic."},{"key":"28_CR4","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2000)"},{"key":"28_CR5","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1997)"},{"key":"28_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2355-7","volume-title":"Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1994","unstructured":"Ebbinghaus, H.-D., Flum, J., Thomas, W.: Mathematical Logic, 2nd edn. Springer, Heidelberg (1994)","edition":"2"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Fagin, R., Stockmeyer, L., Vardi, M.: On monadic NP vs. monadic co-NP. In: The Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pp. 19\u201330 (1993) (Full paper in Information and Computation 120(1), 78\u201392 (1995)","DOI":"10.1006\/inco.1995.1100"},{"key":"28_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"M. Frick","year":"1999","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, Springer, Heidelberg (1999)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), pp. 215\u2013224 (2002)","DOI":"10.1109\/LICS.2002.1029830"},{"key":"28_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Bell Tel. Laboratories (1979)"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1080\/03081089708818520","volume":"43","author":"J. Goldwasser","year":"1997","unstructured":"Goldwasser, J., Klostermeyer, W., Trapp, G.: Characterizing Switch-Setting Problems. Linear and Multilinear Algebra\u00a043, 121\u2013135 (1997)","journal-title":"Linear and Multilinear Algebra"},{"key":"28_CR12","first-page":"132","volume-title":"Symposium on the Theory of Models","author":"W. Hanf","year":"1965","unstructured":"Hanf, W.: Model-theoretic methods in the study of elementary logic. In: Addison, J.W., Henkin, L.A., Tarski, A. (eds.) Symposium on the Theory of Models, pp. 132\u2013145. North-Holland Publ. Co., Amsterdam (1965)"},{"key":"28_CR13","first-page":"81","volume":"55","author":"E.O. Hare","year":"1986","unstructured":"Hare, E.O., Hedetniemi, S.T., Hare, W.R.: Algorithms for Computing the domination number of KxN complete grid graphs. Congr. Numerantium\u00a055, 81\u201392 (1986)","journal-title":"Congr. Numerantium"},{"key":"28_CR14","unstructured":"Hlineny, P., Oum, S., Seese, D., Gottlob, G.: Width Parameters Beyond Tree-width and Their Applications. The Computer Journal, spec. vol. on FPT, pp. 1\u201371(to appear)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/3-540-55488-2_21","volume-title":"Data Structures and Efficient Algorithms","author":"F. Hoefting","year":"1992","unstructured":"Hoefting, F., Lengauer, T., Wanke, E.: Processing of hierarchically defined graphs and graph families. In: Monien, B., Ottmann, T. (eds.) Data Structures and Efficient Algorithms. LNCS, vol.\u00a0594, pp. 44\u201369. Springer, Heidelberg (1992)"},{"key":"28_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, New York (1999)"},{"issue":"4","key":"28_CR17","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamiltonian paths in grid graphs. SIAM Journal of Comp.\u00a011(4), 676\u2013686 (1982)","journal-title":"SIAM Journal of Comp."},{"issue":"3","key":"28_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230180307","volume":"18","author":"K. Iwano","year":"1988","unstructured":"Iwano, K., Steiglitz, K.: Planarity testing of double periodic infinite graphs. Networks\u00a018(3), 205\u2013222 (1988)","journal-title":"Networks"},{"issue":"3","key":"28_CR19","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"R.M. Karp","year":"1967","unstructured":"Karp, R.M., Miller, R.E., Winograd, A.: The organization of computations for uniform recurrence equations. Journal of the ACM\u00a014(3), 563\u2013590 (1967)","journal-title":"Journal of the ACM"},{"key":"28_CR20","first-page":"165","volume-title":"Paths, Flows and VLSI-Layout","author":"M. Kaufmann","year":"1990","unstructured":"Kaufmann, M., Mehlhorn, K.: Routing problems in grid graphs. In: Korte, B., Lovasz, L., Promel, H.J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layout, pp. 165\u2013184. Springer, Heidelberg (1990)"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. B.G.Teubner and John Wiley & Sons, Chichester (1990)","DOI":"10.1007\/978-3-322-92106-2_3"},{"issue":"2","key":"28_CR22","doi-asserted-by":"crossref","first-page":"127","DOI":"10.6028\/jres.110.012","volume":"110","author":"W.F. Mitchell","year":"2005","unstructured":"Mitchell, W.F.: Hamiltonian paths through two- and three-dimensional grids. Journal of Research of the National Institute of Standards and Technology\u00a0110(2), 127\u2013136 (2005)","journal-title":"Journal of Research of the National Institute of Standards and Technology"},{"key":"28_CR23","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/BFb0028825","volume-title":"Fundamentals of Computation Theory","author":"D. Seese","year":"1985","unstructured":"Seese, D.: Tree-partite graphs and the complexity of algorithms (extended abstract). In: Budach, L. (ed.) FCT 1985. LNCS, vol.\u00a0199, pp. 412\u2013421. Springer, Heidelberg (1985)"},{"key":"28_CR25","doi-asserted-by":"crossref","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math. Struct. in Comp. Science, 505\u2013526 (1996)","DOI":"10.1017\/S0960129500070079"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BFb0030338","volume-title":"Mathematical Foundations of Computer Science 1984","author":"K. Wagner","year":"1984","unstructured":"Wagner, K.: The complexity of problems concerning graphs with regularities. In: Chytil, M.P., Koubek, V. (eds.) Mathematical Foundations of Computer Science 1984. LNCS, vol.\u00a0176, pp. 544\u2013552. Springer, Heidelberg (1984) (extended abstract appeared in Proceedings of the 11th. MFCS)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73814-5_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:16:45Z","timestamp":1605763005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73814-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540738138"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73814-5_28","relation":{},"subject":[]}}