{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T11:47:00Z","timestamp":1773834420866,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540538325","type":"print"},{"value":"9783540463108","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-53832-1_29","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:13:42Z","timestamp":1330208022000},"page":"30-40","source":"Crossref","is-referenced-by-count":23,"title":["On the complexity of some coloring games"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/62.322433","volume":"31","author":"A. Adachi","year":"1984","unstructured":"A. Adachi, S. Iwata, and T. Kasai. Some combinatorial game problems require \u03a9(n k) time. J. ACM, 31:361\u2013376, 1984.","journal-title":"J. ACM"},{"key":"3_CR2","series-title":"Technical Report","volume-title":"Classes of graphs with bounded treewidth","author":"H. L. Bodlaender","year":"1986","unstructured":"H. L. Bodlaender. Classes of graphs with bounded treewidth. Technical Report RUU-CS-86-22, Dept. of Computer Science, Utrecht University, Utrecht, 1986."},{"key":"3_CR3","unstructured":"H. L. Bodlaender. Improved self-reduction algorithms for graphs with bounded treewidth. Technical Report RUU-CS-88-29, Dept. of Computer Science, Utrecht University, 1988. To appear in: Proc. Workshop on Graph Theoretic Concepts in Comp. Sc. '89."},{"key":"3_CR4","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1145\/321978.321989","volume":"23","author":"S. Even","year":"1976","unstructured":"S. Even and R. Tarjan. A combinatorial problem which is complete in polynomial space. J. ACM, 23:710\u2013719, 1976.","journal-title":"J. ACM"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"A. Fraenkel, M. Garey, D. Johnson, T. Schaefer, and Y. Yesha. The complexity of checkers on an n \u00d7 n board \u2014 preliminary version. In Proc. 19th Annual Symp. on Foundations of Computer Science, pages 55\u201364, 1978.","DOI":"10.1109\/SFCS.1978.36"},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0097-3165(87)90074-4","volume":"46","author":"A. Fraenkel","year":"1987","unstructured":"A. Fraenkel and E. Goldschmidt. Pspace-hardness of some combinatorial games. J. Combinatorial Theory ser. A, 46:21\u201338, 1987.","journal-title":"J. Combinatorial Theory ser. A"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0097-3165(81)90016-9","volume":"31","author":"A. Fraenkel","year":"1981","unstructured":"A. Fraenkel and D. Lichtenstein. Computing a perfect strategy for n by n chess requires time exponential in n. J. Combinatorial Theory ser. A, 31:199\u2013214, 1981.","journal-title":"J. Combinatorial Theory ser. A"},{"key":"3_CR8","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0196-6774(83)90019-6","volume":"4","author":"D. Johnson","year":"1983","unstructured":"D. Johnson. The NP-completeness column: An ongoing guide. J. Algorithms, 4:397\u2013411, 1983.","journal-title":"J. Algorithms"},{"key":"3_CR10","unstructured":"Personal communication. 1990."},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"T. Lengauer. Black-white pebbles and graph separation. Acta Inf., 16:465\u2013475, 1981.","journal-title":"Acta Inf."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1145\/322186.322201","volume":"27","author":"D. Lichtenstein","year":"1980","unstructured":"D. Lichtenstein and M. Sipser. Go is polynomial-space hard. J. ACM, 27:393\u2013401, 1980.","journal-title":"J. ACM"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/0213018","volume":"13","author":"J. Robson","year":"1984","unstructured":"J. Robson. N by N Checkers is exptime complete. SIAM J. Comput., 13:252\u2013267, 1984.","journal-title":"SIAM J. Comput."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proc. 10th Symp. on Theory of Computation, pages 216\u2013226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T. J. Schaefer","year":"1978","unstructured":"T. J. Schaefer. On the complexity of some two-person perfect-information games. J. Comp. Syst. Sc., 16:185\u2013225, 1978.","journal-title":"J. Comp. Syst. Sc."},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0208013","volume":"8","author":"L. J. Stockmeyer","year":"1979","unstructured":"L. J. Stockmeyer and A. K. Chandra. Provably difficult combinatorial games. SIAM J. Comput., 8:151\u2013174, 1979.","journal-title":"SIAM J. Comput."},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215\u2013225, 1975.","journal-title":"J. ACM"}],"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\/3-540-53832-1_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:50:57Z","timestamp":1605646257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53832-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540538325","9783540463108"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-53832-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}