{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:02:53Z","timestamp":1742990573656,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031521126"},{"type":"electronic","value":"9783031521133"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-52113-3_19","type":"book-chapter","created":{"date-parts":[[2024,2,7]],"date-time":"2024-02-07T00:02:50Z","timestamp":1707264170000},"page":"269-282","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of\u00a0Online Graph Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3993-222X","authenticated-orcid":false,"given":"Janosch","family":"Fuchs","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7789-8870","authenticated-orcid":false,"given":"Christoph","family":"Gr\u00fcne","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4617-3540","authenticated-orcid":false,"given":"Tom","family":"Jan\u00dfen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,7]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Agrawal, M., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. In: Leighton, F.T., Shor, P.W. (eds.) Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 730\u2013738 (1997). https:\/\/doi.org\/10.1145\/258533.258671","key":"19_CR1","DOI":"10.1145\/258533.258671"},{"issue":"6","key":"19_CR2","doi-asserted-by":"publisher","first-page":"1366","DOI":"10.1007\/s00224-017-9797-2","volume":"62","author":"M B\u00f6hm","year":"2018","unstructured":"B\u00f6hm, M., Vesel\u00fd, P.: Online chromatic number is pspace-complete. Theory Comput. Syst. 62(6), 1366\u20131391 (2018). https:\/\/doi.org\/10.1007\/s00224-017-9797-2","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"19_CR3","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1007\/s00224-016-9688-y","volume":"61","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: The advice complexity of a class of hard online problems. Theory Comput. Syst. 61(4), 1128\u20131177 (2017). https:\/\/doi.org\/10.1007\/s00224-016-9688-y","journal-title":"Theory Comput. Syst."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.dam.2017.02.025","volume":"246","author":"J Boyar","year":"2018","unstructured":"Boyar, J., Kudahl, C.: Adding isolated vertices makes some greedy online algorithms optimal. Discret. Appl. Math. 246, 12\u201321 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.02.025","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"publisher","unstructured":"Fraenkel, A.S., Goldschmidt, E.: Pspace-hardness of some combinatorial games. J. Comb. Theory Ser. A 46(1), 21\u201338 (1987). https:\/\/doi.org\/10.1016\/0097-3165(87)90074-4","key":"19_CR5","DOI":"10.1016\/0097-3165(87)90074-4"},{"doi-asserted-by":"crossref","unstructured":"Fuchs, J., Gr\u00fcne, C., Jan\u00dfen, T.: The complexity of online graph games (2023)","key":"19_CR6","DOI":"10.1007\/978-3-031-52113-3_19"},{"unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)","key":"19_CR7"},{"doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M.: Online coloring known graphs. Electron. J. Comb. 7 (2000). https:\/\/doi.org\/10.37236\/1485","key":"19_CR8","DOI":"10.37236\/1485"},{"issue":"2","key":"19_CR9","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1016\/S0304-3975(01)00411-X","volume":"289","author":"MM Halld\u00f3rsson","year":"2002","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Taketomi, S.: Online independent sets. Theor. Comput. Sci. 289(2), 953\u2013962 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00411-X","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Harutyunyan, H.A., Pankratov, D., Racicot, J.: Online domination: the value of getting to know all your neighbors. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science, MFCS, vol. 202, pp. 57:1\u201357:21 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.57","key":"19_CR10","DOI":"10.4230\/LIPIcs.MFCS.2021.57"},{"key":"19_CR11","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. IRSS, pp. 85\u2013103. Springer, Cham (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-319-18173-8_23","volume-title":"Algorithms and Complexity","author":"C Kudahl","year":"2015","unstructured":"Kudahl, C.: Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 313\u2013324. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18173-8_23"},{"issue":"1","key":"19_CR13","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127\u2013150 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90263-2","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Aho, A.V., et al. (eds.) Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 1\u20139 (1973). https:\/\/doi.org\/10.1145\/800125.804029","key":"19_CR14","DOI":"10.1145\/800125.804029"},{"doi-asserted-by":"publisher","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming (extended abstract). In: 37th Annual Symposium on Foundations of Computer Science, pp. 617\u2013626 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548521","key":"19_CR15","DOI":"10.1109\/SFCS.1996.548521"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2024: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-52113-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T20:04:38Z","timestamp":1711569878000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-52113-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031521126","9783031521133"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-52113-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 February 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cochem","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 February 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 February 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.uni-trier.de\/index.php?id=90670&L=2","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.11","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}