{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:26:20Z","timestamp":1740108380274,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T00:00:00Z","timestamp":1478044800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"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"}]},{"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00236-016-0283-0","type":"journal-article","created":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T13:52:21Z","timestamp":1478094741000},"page":"57-80","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online edge coloring of paths and trees with a fixed number of colors"],"prefix":"10.1007","volume":"55","author":[{"given":"Lene M.","family":"Favrholdt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper W.","family":"Mikkelsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,2]]},"reference":[{"issue":"2","key":"283_CR1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1023\/A:1022985808959","volume":"6","author":"E Bach","year":"2003","unstructured":"Bach, E., Boyar, J., Epstein, L., Favrholdt, L.M., Jiang, T., Larsen, K.S., Lin, G.-H., van Stee, R.: Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem. J. Sched. 6(2), 131\u2013147 (2003)","journal-title":"J. Sched."},{"issue":"5","key":"283_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0020-0190(92)90209-E","volume":"44","author":"A Bar-Noy","year":"1992","unstructured":"Bar-Noy, A., Motwani, R., Naor, J.S.: The greedy algorithm is optimal for on-line edge coloring. Inf. Process. Lett. 44(5), 251\u2013253 (1992)","journal-title":"Inf. Process. Lett."},{"key":"283_CR3","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"2","key":"283_CR4","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/1240233.1240245","volume":"3","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for online algorithms. ACM Trans. Algorithms 3(2), 22 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"283_CR5","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1016\/j.jcss.2007.03.001","volume":"73","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst-order ratio applied to paging. J. Comput. Syst. Sci. 73, 818\u2013843 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"283_CR6","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J Boyar","year":"1999","unstructured":"Boyar, J., Larsen, K.S.: The seat reservation problem. Algorithmica 25(4), 403\u2013417 (1999)","journal-title":"Algorithmica"},{"issue":"17","key":"283_CR7","doi-asserted-by":"crossref","first-page":"1894","DOI":"10.1016\/j.dam.2010.08.010","volume":"158","author":"Z-Z Chen","year":"2010","unstructured":"Chen, Z.-Z., Konno, S., Matsushita, Y.: Approximating maximum edge 2-coloring in simple graphs. Discrete Appl. Math. 158(17), 1894\u20131901 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"16\u201318","key":"283_CR8","doi-asserted-by":"crossref","first-page":"1734","DOI":"10.1016\/j.tcs.2010.01.015","volume":"411","author":"MR Ehmsen","year":"2010","unstructured":"Ehmsen, M.R., Favrholdt, L.M., Kohrt, J.S., Mihai, R.: Comparing first-fit and next-fit for online edge coloring. Theor. Comput. Sci. 411(16\u201318), 1734\u20131741 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"283_CR9","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/s00453-002-0992-3","volume":"35","author":"LM Favrholdt","year":"2003","unstructured":"Favrholdt, L.M., Nielsen, M.N.: On-line edge-coloring with a fixed number of colors. Algorithmica 35(2), 176\u2013191 (2003)","journal-title":"Algorithmica"},{"key":"283_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Ofek, E., Wieder, U.: Approximating maximum edge coloring in multigraphs. In: Proceedings of the 5th international workshop on approximation algorithms for combinatorial optimization, volume 2462 of LNCS, pp. 108\u2013121 (2002)","DOI":"10.1007\/3-540-45753-4_11"},{"issue":"3","key":"283_CR11","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1137\/120899765","volume":"28","author":"M Kami\u0144ski","year":"2014","unstructured":"Kami\u0144ski, M., Kowalik, \u0141.: Beyond the Vizing\u2019s bound for at most seven colors. SIAM J. Discrete Math. 28(3), 1334\u20131362 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"283_CR12","doi-asserted-by":"crossref","first-page":"77","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, 77\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"283_CR13","doi-asserted-by":"crossref","unstructured":"Kierstead, H.A.: Coloring graphs on-line. In Online Algorithms, pp. 281\u2013305. Springer (1998)","DOI":"10.1007\/BFb0029574"},{"issue":"17","key":"283_CR14","doi-asserted-by":"crossref","first-page":"3593","DOI":"10.1016\/j.dam.2009.04.002","volume":"157","author":"A Kosowski","year":"2009","unstructured":"Kosowski, A.: Approximating the maximum 2- and 3-edge-colorable subgraph problems. Discrete Appl. Math. 157(17), 3593\u20133600 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"12","key":"283_CR15","doi-asserted-by":"crossref","first-page":"4166","DOI":"10.1016\/j.disc.2008.11.017","volume":"309","author":"R Rizzi","year":"2009","unstructured":"Rizzi, R.: Approximating the maximum 3-edge-colorable subgraph problem. Discrete Math. 309(12), 4166\u20134170 (2009)","journal-title":"Discrete Math."},{"issue":"2","key":"283_CR16","doi-asserted-by":"crossref","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":"283_CR17","doi-asserted-by":"crossref","unstructured":"Yao, A.C-C.: Probabilistic computations: toward a unified measure of complexity (extended abstract). In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0283-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0283-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0283-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T02:56:15Z","timestamp":1568516175000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0283-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,2]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["283"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0283-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2016,11,2]]}}}