{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:43:16Z","timestamp":1770741796975,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-7014-00041"],"award-info":[{"award-number":["DFF-7014-00041"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-0135-00018B"],"award-info":[{"award-number":["DFF-0135-00018B"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["VKR023219"],"award-info":[{"award-number":["VKR023219"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00453-022-00944-w","type":"journal-article","created":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T18:02:46Z","timestamp":1645812166000},"page":"1916-1951","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Relaxing the Irrevocability Requirement for Online Graph Algorithms"],"prefix":"10.1007","volume":"84","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kotrb\u010d\u00edk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"944_CR1","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S.: Online maximum matching with recourse. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, pp. 8:1\u20138:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik GmbH (2018)"},{"key":"944_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Fiat, A., Leonardi, S.: Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In: 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 531\u2013540. ACM (1996)","DOI":"10.1145\/237814.238001"},{"key":"944_CR3","doi-asserted-by":"crossref","unstructured":"Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrb\u010d\u00edk, M., Larsen., K.S.: Online dominating set. Algorithmica 81(5), 1938\u20131964 (2019)","DOI":"10.1007\/s00453-018-0519-1"},{"key":"944_CR4","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M., Kotrb\u010d\u00edk, M., Larsen., K.S.: Relaxing the irrevocability requirement for online graph algorithms. In: 15th International Algorithms and Data Structures Symposium (WADS), Lecture Notes in Computer Science, vol. 10389, pp. 217\u2013228. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_19"},{"issue":"4","key":"944_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1142\/S0129054115500239","volume":"26","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: The frequent items problem in online streaming under various performance measures. Int. J. Found. Comput. Sci. 26(4), 413\u2013439 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"944_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1202\u20131216. SIAM (2015)","DOI":"10.1137\/1.9781611973730.80"},{"issue":"1","key":"944_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00224-014-9566-4","volume":"58","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Je\u017c, \u0141, Sgall, J.: Online knapsack revisited. Theory Comput. Syst. 58(1), 153\u2013190 (2016)","journal-title":"Theory Comput. Syst."},{"key":"944_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theoret. Comput. Sci. 332, 83\u2013108 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"944_CR9","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discret. Math. 25(3), 1251\u20131265 (2011)","journal-title":"SIAM J. Discret. Math."},{"key":"944_CR10","unstructured":"Epstein, L., Levin, A., Segev, D., Weimann, O.: Improved bounds for online preemptive matching. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a020, pp. 389\u2013399. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik GmbH (2013)"},{"issue":"2\u20133","key":"944_CR11","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoret. Comput. Sci. 348(2\u20133), 207\u2013216 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"944_CR12","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jagm.1996.0821","volume":"23","author":"JA Garay","year":"1997","unstructured":"Garay, J.A., Gopal, I.S., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. J. Algorithms 23(1), 180\u2013194 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"944_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955276","volume":"45","author":"A Gu","year":"2016","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: Maintaining a constant-competitive Steiner tree online. SIAM J. Comput. 45(1), 1\u201328 (2016)","journal-title":"SIAM J. Comput."},{"key":"944_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Online Steiner tree with deletions. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 455\u2013467. SIAM (2014)","DOI":"10.1137\/1.9781611973402.34"},{"key":"944_CR15","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.tcs.2014.10.017","volume":"562","author":"X Han","year":"2015","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theoret. Comput. Sci. 562, 395\u2013405 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"944_CR16","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2013.09.013","volume":"540","author":"X Han","year":"2014","unstructured":"Han, X., Kawase, Y., Makino, K., Guo, H.: Online removable knapsack problem under convex function. Theoret. Comput. Sci. 540, 62\u201369 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"944_CR17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.tcs.2015.09.021","volume":"609","author":"X Han","year":"2016","unstructured":"Han, X., Makino, K.: Online minimization knapsack problem. Theoret. Comput. Sci. 609, 185\u2013196 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"944_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discret. Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"944_CR19","doi-asserted-by":"crossref","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: 29th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 2380, pp. 293\u2013305. Springer (2002)","DOI":"10.1007\/3-540-45465-9_26"},{"key":"944_CR20","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1002\/net.21559","volume":"64","author":"P Jaillet","year":"2014","unstructured":"Jaillet, P., Lu, X.: Online traveling salesman problems with rejection options. Networks 64, 84\u201395 (2014)","journal-title":"Networks"},{"key":"944_CR21","volume-title":"Graph Coloring Problems","author":"TR Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, NJ (1995)"},{"key":"944_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"944_CR23","doi-asserted-by":"crossref","unstructured":"Kocic, V.L., Ladas, G.: Global behavior of nonlinear difference equations of higher order with applications. Mathematics and Its Applications, vol. 256. Springer (1993)","DOI":"10.1007\/978-94-017-1703-8"},{"key":"944_CR24","doi-asserted-by":"crossref","unstructured":"Komm, D.: An Introduction to Online Computation: Determinism, Randomization. Springer, Advice (2016)","DOI":"10.1007\/978-3-319-42749-2_2"},{"key":"944_CR25","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., Kudahl, C.: Advice complexity of the online induced subgraph problem. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a058, pp. 59:1\u201359:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"944_CR26","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1978","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2, 65\u201374 (1978)","journal-title":"Ann. Discrete Math."},{"key":"944_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4400-4","volume-title":"The Design and Analysis of Algorithms","author":"DC Kozen","year":"1992","unstructured":"Kozen, D.C.: The Design and Analysis of Algorithms. Springer, Berlin (1992)"},{"key":"944_CR28","doi-asserted-by":"crossref","unstructured":"Ladas, G., Philos, C.G., Sficas, Y.G.: Necessary and sufficient conditions for the oscillation of difference equations. Libertas Mathematica 9 (1989)","DOI":"10.1155\/S1048953389000080"},{"key":"944_CR29","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976)"},{"issue":"3","key":"944_CR30","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/130917703","volume":"45","author":"N Megow","year":"2016","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. SIAM J. Comput. 45(3), 859\u2013880 (2016)","journal-title":"SIAM J. Comput."},{"key":"944_CR31","unstructured":"Rawitz, D., Ros\u00e9n, A.: Online budgeted maximum coverage. In: 24th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a057, pp. 73:1\u201373:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik GmbH (2016)"},{"key":"944_CR32","doi-asserted-by":"crossref","unstructured":"Rossmanith, P.: On the advice complexity of online edge- and node-deletion problems. In: Adventures Between Lower Bounds and Higher Altitudes. Lecture Notes in Computer Science, vol. 11011, pp. 449\u2013462. Springer (2018)","DOI":"10.1007\/978-3-319-98355-4_26"},{"key":"944_CR33","doi-asserted-by":"crossref","unstructured":"Saha, B., Getoor, L.: On maximum coverage in the streaming model & application to multi-topic blog-watch. In: SIAM International Conference on Data Mining, pp. 697\u2013708. SIAM (2009)","DOI":"10.1137\/1.9781611972795.60"},{"issue":"2","key":"944_CR34","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"944_CR35","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Data structures and network algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a044. SIAM (1983)","DOI":"10.1137\/1.9781611970265"},{"issue":"3","key":"944_CR36","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1002\/jgt.3190050304","volume":"5","author":"C Thomassen","year":"1981","unstructured":"Thomassen, C.: Kuratowski\u2019s theorem. J. Gr. Theory 5(3), 225\u2013241 (1981)","journal-title":"J. Gr. Theory"},{"issue":"1","key":"944_CR37","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1077464.1077472","volume":"1","author":"DED Vinkemeier","year":"2005","unstructured":"Vinkemeier, D.E.D., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM Trans. Algorithms 1(1), 107\u2013122 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"944_CR38","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57(3), 509\u2013533 (1935)","journal-title":"Am. J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00944-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00944-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00944-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:05:15Z","timestamp":1655982315000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00944-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["944"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00944-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,25]]},"assertion":[{"value":"29 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}