{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:33:14Z","timestamp":1774333994953,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":26,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-7127-7_20","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:07:07Z","timestamp":1770977227000},"page":"293-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity and\u00a0Algorithms for\u00a0Arc-Kayles and\u00a0Non-disconnecting Arc-Kayles"],"prefix":"10.1007","author":[{"given":"Kyle","family":"Burke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Dailly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nacim","family":"Oijid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Albert, M., Nowakowski, R., Wolfe, D.: Lessons in Play: An Introduction to Combinatorial Game Theory. AK Peters\/CRC Press (2019)","DOI":"10.1201\/9781482243048"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.tcs.2018.06.018","volume":"746","author":"L Beaudou","year":"2018","unstructured":"Beaudou, L., et al.: Octal games on graphs: the game 0.33 on subdivided stars and bistars. Theoret. Comput. Sci. 746, 19\u201335 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"9","key":"20_CR3","doi-asserted-by":"publisher","first-page":"2533","DOI":"10.1007\/s00453-022-00973-5","volume":"84","author":"J Bensmail","year":"2022","unstructured":"Bensmail, J., Fioravantes, F., Mc Inerney, F., Nisse, N.: The largest connected subgraph game. Algorithmica 84(9), 2533\u20132555 (2022)","journal-title":"Algorithmica"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays. AK Peters\/CRC Press (2001\u20132004)","DOI":"10.1201\/9780429487309"},{"key":"20_CR5","unstructured":"Burke, K., Dailly, A., Oijid, N.: Complexity and algorithms for arc-kayles and non-disconnecting arc-kayles. arXiv preprint arXiv:2404.10390 (2024)"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1017\/9781108641999.010","volume":"5","author":"K Burke","year":"2019","unstructured":"Burke, K., George, O.: A PSPACE-complete graph nim. Games No Chance 5, 259\u2013269 (2019)","journal-title":"Games No Chance"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Conway, J.H.: On Numbers and Games. CRC Press (2000)","DOI":"10.1201\/9781439864159"},{"key":"20_CR8","unstructured":"Dailly, A.: Criticalit\u00e9, identification et jeux de suppression de sommets dans les graphes: Des \u00e9toiles plein les jeux. Ph.D. thesis, Universit\u00e9 de Lyon (2018)"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s00182-018-0639-5","volume":"48","author":"A Dailly","year":"2019","unstructured":"Dailly, A., Gledel, V., Heinrich, M.: A generalization of Arc-Kayles. Int. J. Game Theory 48, 491\u2013511 (2019)","journal-title":"Int. J. Game Theory"},{"key":"20_CR10","unstructured":"Dailly, A., Moncel, J., Parreau, A.: Connected subtraction games on subdivided stars. Integers: Electron. J. Comb. Number Theory 19, G3 (2019)"},{"key":"20_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114274","volume":"982","author":"E Duch\u00eane","year":"2024","unstructured":"Duch\u00eane, E., Oijid, N., Parreau, A.: Bipartite instances of INFLUENCE. Theoret. Comput. Sci. 982, 114274 (2024)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"20_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/S0304-3975(03)00292-5","volume":"304","author":"M Fukuyama","year":"2003","unstructured":"Fukuyama, M.: A Nim game played on graphs. Theoret. Comput. Sci. 304(1\u20133), 387\u2013399 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"20_CR13","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/S0304-3975(03)00293-7","volume":"304","author":"M Fukuyama","year":"2003","unstructured":"Fukuyama, M.: A Nim game played on graphs II. Theoret. Comput. Sci. 304(1\u20133), 401\u2013419 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"20_CR14","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1038\/scientificamerican0273-106","volume":"230","author":"M Gardner","year":"1974","unstructured":"Gardner, M.: Mathematical games: cram, crosscram and quadraphage: new games having elusive winning strategies. Sci. Am. 230(2), 106\u2013108 (1974)","journal-title":"Sci. Am."},{"key":"20_CR15","first-page":"6","volume":"2","author":"PM Grundy","year":"1939","unstructured":"Grundy, P.M.: Mathematics and games. Eureka 2, 6\u20138 (1939)","journal-title":"Eureka"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Guy, R.K., Smith, C.A.: The G-values of various games. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 52, no. 3, pp. 514\u2013526. Cambridge University Press (1956)","DOI":"10.1017\/S0305004100031509"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kiya, H., Lampis, M., Ono, H., Yoshiwatari, K.: Faster winner determination algorithms for (Colored) Arc Kayles. J. Comput. Syst. Sci. 103716 (2025)","DOI":"10.1016\/j.jcss.2025.103716"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kiya, H., Ono, H., Yoshiwatari, K.: Winner determination algorithms for graph games with matching structures. Algorithmica 1\u201317 (2023)","DOI":"10.1007\/s00453-023-01136-w"},{"key":"20_CR19","first-page":"A86","volume":"16","author":"MA Huggan","year":"2016","unstructured":"Huggan, M.A., Stevens, B.: Polynomial time graph families for Arc Kayles. Integers 16, A86 (2016)","journal-title":"Integers"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-54423-1_3","volume-title":"LATIN 2014: Theoretical Informatics","author":"M Lampis","year":"2014","unstructured":"Lampis, M., Mitsou, V.: The computational complexity of the game of set and its theoretical applications. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 24\u201334. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_3"},{"key":"20_CR21","unstructured":"Lemoine, J., Viennot, S.: Computation records of normal and mis\u00e8re cram. http:\/\/sprouts.tuxfamily.org\/wiki\/doku.php?id=records#cram"},{"issue":"2","key":"20_CR22","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: 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":"20_CR23","doi-asserted-by":"crossref","unstructured":"Siegel, A.N.: Combinatorial Game Theory, vol.\u00a0146. American Mathematical Society (2013)","DOI":"10.1090\/gsm\/146"},{"key":"20_CR24","first-page":"438","volume":"41","author":"R Sprague","year":"1935","unstructured":"Sprague, R.: \u00dcber mathematische kampfspiele. Tohoku Math. J. First Series 41, 438\u2013444 (1935)","journal-title":"Tohoku Math. J. First Series"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.3233\/ICG-180064","volume":"40","author":"JW Uiterwijk","year":"2018","unstructured":"Uiterwijk, J.W.: Construction and investigation of cram endgame databases. ICGA J. 40(4), 425\u2013437 (2018)","journal-title":"ICGA J."},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Uiterwijk, J.W.: Solving cram using combinatorial game theory. In: Advances in Computer Games, pp. 91\u2013105. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-65883-0_8"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:11:32Z","timestamp":1774325492000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}