{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T09:46:44Z","timestamp":1747388804124},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T00:00:00Z","timestamp":1683849600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T00:00:00Z","timestamp":1683849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00493-023-00026-7","type":"journal-article","created":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T08:02:27Z","timestamp":1683878547000},"page":"595-612","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["6-Uniform Maker-Breaker Game is PSPACE-Complete"],"prefix":"10.1007","volume":"43","author":[{"given":"Md Lutfar","family":"Rahman","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,12]]},"reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"2085","DOI":"10.1016\/S0304-3975(02)00491-7","volume":"290","author":"A Arratia","year":"2003","unstructured":"Arratia, A., Stewart, I.: A note on first-order projections and games. Theoret. Comput. Sci. 290(3), 2085\u20132093 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M., Tarjan, R.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.07.025","volume":"648","author":"B Bre\u0161ar","year":"2016","unstructured":"Bre\u0161ar, B., Dorbec, P., Klav\u017ear, S., Ko\u0161mrlj, G., Renault, G.: Complexity of the game domination problem. Theoret. Comput. Sci. 648, 1\u20137 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Byskov, J.: Maker-Maker and Maker-Breaker games are PSPACE-complete. Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University (2004)","DOI":"10.7146\/brics.v11i14.21839"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0167-5060(08)70335-2","volume":"2","author":"V Chv\u00e1tal","year":"1978","unstructured":"Chv\u00e1tal, V., Erd\u0151s, P.: Biased positional games. Ann. Discrete Math. 2, 221\u2013229 (1978)","journal-title":"Ann. Discrete Math."},{"key":"26_CR6","first-page":"36","volume":"824\u2013825","author":"E Costa","year":"2019","unstructured":"Costa, E., Pessoa, V.L., Sampaio, R., Soares, R.: PSPACE-completeness of two graph coloring games. Theoret. Comput. Sci. 824\u2013825, 36\u201345 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Demaine, E., Hearn, R.: Constraint logic: a uniform framework for modeling computation as games. In: Proceedings of the 23rd Conference on Computational Complexity (CCC). IEEE, pp. 149\u2013162 (2008)","DOI":"10.1109\/CCC.2008.35"},{"issue":"9","key":"26_CR8","doi-asserted-by":"publisher","first-page":"111955","DOI":"10.1016\/j.disc.2020.111955","volume":"343","author":"\u00c9 Duch\u00eane","year":"2020","unstructured":"Duch\u00eane, \u00c9., Gledel, V., Parreau, A., Renault, G.: Maker-Breaker domination game. Discret. Math. 343(9), 111955 (2020)","journal-title":"Discret. Math."},{"issue":"3","key":"26_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Selfridge, J.: On a combinatorial game. J. Combin. Theory Ser. A 14(3), 1 (1973)","journal-title":"J. Combin. Theory Ser. A"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Fenner, S., Grier, D., Messner, J., Schaeffer, L., Thierauf, T.: Game values and computational complexity: An analysis via black-white combinatorial games. In: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC). Springer, pp. 689\u2013699 (2015)","DOI":"10.1007\/978-3-662-48971-0_58"},{"issue":"1","key":"26_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0097-3165(87)90074-4","volume":"46","author":"A Fraenkel","year":"1987","unstructured":"Fraenkel, A., Goldschmidt, E.: PSPACE-hardness of some combinatorial games. J. Combin. Theory Ser. A 46(1), 21\u201338 (1987)","journal-title":"J. Combin. Theory Ser. A"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.dam.2019.11.004","volume":"282","author":"V Gledel","year":"2020","unstructured":"Gledel, V., Henning, M., Ir\u0161i\u010d, V., Klav\u017ear, S.: Maker-Breaker total domination game. Discret. Appl. Math. 282, 96\u2013107 (2020)","journal-title":"Discret. Appl. Math."},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Hearn, R.: Amazons, Konane, and cross purposes are PSPACE-complete. In: Games of No Chance 3, Mathematical Sciences Research Institute Publications. Cambridge University Press, pp. 287\u2013306 (2009)","DOI":"10.1017\/CBO9780511807251.015"},{"key":"26_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0825-5","volume-title":"Positional Games","author":"D Hefetz","year":"2014","unstructured":"Hefetz, D., Krivelevich, M., Stojakovi\u0107, M.S.: Positional Games. Birkh\u00e4user, Basel (2014)"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Weak positional games on hypergraphs of rank three. In: Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EuroComb). Discrete Mathematics & Theoretical Computer Science, pp. 31\u201336 (2005)","DOI":"10.46298\/dmtcs.3422"},{"issue":"4","key":"26_CR16","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/0112059","volume":"12","author":"A Lehman","year":"1964","unstructured":"Lehman, A.: A solution of the Shannon switching game. J. Soc. Ind. Appl. Math. 12(4), 687\u2013725 (1964)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Marcilon, T., Martins, N., Sampaio, R.: Hardness of variants of the graph coloring game. In: Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN). Springer, pp. 348\u2013359 (2020)","DOI":"10.1007\/978-3-030-61792-9_28"},{"key":"26_CR18","unstructured":"Morawietz, N., Gr\u00fcttemeier, N., Komusiewicz, C., Sommer, F.: Colored cut games. In: Proceedings of the 40th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Schloss Dagstuhl, pp. 1\u201317 (2020)"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Rahman, M.L., Watson, T.: Tractable unordered 3-CNF games. In: Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN). Springer, pp. 360\u2013372 (2020)","DOI":"10.1007\/978-3-030-61792-9_29"},{"issue":"3","key":"26_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3397478","volume":"12","author":"ML Rahman","year":"2020","unstructured":"Rahman, M.L., Watson, T.: Complexity of unordered CNF games. ACM Trans. Comput. Theory 12(3), 1\u201318 (2020)","journal-title":"ACM Trans. Comput. Theory"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: Complexity of decision problems based on finite two-person perfect-information games. In: Proceedings of the 8th Symposium on Theory of Computing (STOC). ACM, pp. 41\u201349 (1976)","DOI":"10.1145\/800113.803629"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T Schaefer","year":"1978","unstructured":"Schaefer, T.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16(2), 185\u2013225 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Slany, W.: The complexity of graph Ramsey games. In: Proceedings of the 2nd International Conference on Computers and Games (CG). Springer, pp. 186\u2013203 (2000)","DOI":"10.1007\/3-540-45579-5_12"},{"issue":"1","key":"26_CR24","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/S0304-3975(01)00179-7","volume":"289","author":"W Slany","year":"2002","unstructured":"Slany, W.: Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. Theoret. Comput. Sci. 289(1), 829\u2013843 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L., Albert, M.: Word problems requiring exponential time. In: Proceedings of the 5th Symposium on Theory of Computing (STOC). ACM, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"issue":"4","key":"26_CR26","doi-asserted-by":"publisher","first-page":"485","DOI":"10.7155\/jgaa.00235","volume":"15","author":"S Teramoto","year":"2011","unstructured":"Teramoto, S., Demaine, E., Uehara, R.: The Voronoi game on graphs and its complexity. J. Graph Algorithms Appl. 15(4), 485\u2013501 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"26_CR27","unstructured":"van Rijn, J., Vis, J.: Complexity and retrograde analysis of the game Dou Shou Qi. In: Proceedings of the 25th Benelux Conference on Artificial Intelligence (BNAIC) (2013)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00026-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00026-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00026-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T12:06:20Z","timestamp":1692360380000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00026-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,12]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["26"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00026-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,12]]},"assertion":[{"value":"4 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}