{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:40:52Z","timestamp":1765608052380},"publisher-location":"Berlin\/Heidelberg","reference-count":16,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540156895"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028825","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T17:15:07Z","timestamp":1138209307000},"page":"412-421","source":"Crossref","is-referenced-by-count":25,"title":["Tree-partite graphs and the complexity of algorithms"],"prefix":"10.1007","author":[{"given":"D.","family":"Seese","sequence":"first","affiliation":[]}],"member":"297","reference":[{"volume-title":"Handbook of Mathematical Logic","year":"1977","key":"41_CR1","unstructured":"J. Barwise (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam 1977."},{"key":"41_CR2","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s, Extremal Graph Theory, Academic Press, London 1978."},{"key":"41_CR3","volume-title":"Mathematical Logic, Undergraduate Texts in Mathematics","author":"H.D. Ebbinghaus","year":"1984","unstructured":"H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic, Undergraduate Texts in Mathematics, Springer-Verlag, New-York, 1984."},{"key":"41_CR4","unstructured":"P. van Emde Boas, Dominoes are Forever, preprint 1983."},{"key":"41_CR5","first-page":"27","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in Complexity of Computation, (ed. R. Karp), SIAM \u2014 AMS Proc. 7, 1974, pp 27\u201341.","journal-title":"SIAM \u2014 AMS Proc."},{"key":"41_CR6","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco 1978."},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"N. Immerman, Languages Which Capture Complexity Classes, acm-proceedings of the 15 annual acm symp. on the theory of computing, 1983, pp. 347\u2013354.","DOI":"10.1145\/800061.808765"},{"key":"41_CR8","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"M.O. Rabin, Decidability of second order theories and automata on infinite trees, Trans. Am. Math. Soc. 141, 1969, 1\u201335.","journal-title":"Trans. Am. Math. Soc."},{"key":"41_CR9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"B 35","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P.D. Seymour, Graph minors I. Excluding a forest, J. Combin. Theory Ser. B 35, 1983, 39\u201361.","journal-title":"J. Combin. Theory Ser."},{"key":"41_CR10","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"B 36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P.D. Seymour, Graph Minors III. Planar Tree-Width, J. Combin. Theory Ser. B 36, 1984, 49\u201364.","journal-title":"J. Combin. Theory Ser."},{"key":"41_CR11","unstructured":"P. Scheffler, personal communication."},{"key":"41_CR12","unstructured":"D.G. Seese, Entscheidbarkeits-und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen, Dissertation, Humboldt-Universit\u00e4t zu Berlin, 1976."},{"issue":"6","key":"41_CR13","first-page":"772","volume":"XXIV","author":"D.G. Seese","year":"1975","unstructured":"D.G. Seese, Ein Unentscheidbarkeitskriterium, Wiss. Z. der Humboldt-Univ. zu Berlin Math.-Nat. R. XXIV, 1975,6, 772\u2013780.","journal-title":"Wiss. Z. der Humboldt-Univ. zu Berlin Math.-Nat. R."},{"key":"41_CR14","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/mana.19790870103","volume":"87","author":"D.G. Seese","year":"1979","unstructured":"D.G. Seese, Some Graph Theoretical Operations and Decidability, Math. Nachr. 87, 1979, 15\u201321.","journal-title":"Math. Nachr."},{"issue":"3","key":"41_CR15","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs, J. of the Association for Computing Machinery, Vol. 29, No. 3, 1982, 623\u2013641.","journal-title":"J. of the Association for Computing Machinery"},{"key":"41_CR16","first-page":"129","volume-title":"Selected Topics in Graph Theory 2","author":"C. Thomassen","year":"1983","unstructured":"C. Thomassen, Infinite Graphs, in Selected Topics in Graph Theory 2, L.W. Beineke and R.J. Wilson (ed.), Acad. press, 1983, London, 129\u2013160."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028825.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:59:11Z","timestamp":1607551151000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540156895"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028825","relation":{},"subject":[]}}