{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:39:19Z","timestamp":1743021559077,"version":"3.40.3"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319182629"},{"type":"electronic","value":"9783319182636"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-18263-6_16","type":"book-chapter","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T14:41:38Z","timestamp":1429713698000},"page":"181-192","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Dual Edge Coloring of Paths and Trees"],"prefix":"10.1007","author":[{"given":"Lene M.","family":"Favrholdt","sequence":"first","affiliation":[]},{"given":"Jesper W.","family":"Mikkelsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"issue":"5","key":"16_CR1","doi-asserted-by":"publisher","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.: The greedy algorithm is optimal for on-line edge coloring. Inf. Process. Lett. 44(5), 251\u2013253 (1992)","journal-title":"Inf. Process. Lett."},{"key":"16_CR2","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":"16_CR3","doi-asserted-by":"publisher","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":"16_CR4","doi-asserted-by":"publisher","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":"17","key":"16_CR5","doi-asserted-by":"publisher","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. Discret. Appl. Math. 158(17), 1894\u20131901 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"16\u201318","key":"16_CR6","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Favrholdt, L.M., Mikkelsen, J.W.: Online dual edge coloring of paths and trees. ArXiv e-prints, 1405.3817 [cs.DS] (2014)","key":"16_CR7","DOI":"10.1007\/978-3-319-18263-6_16"},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","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":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-45753-4_11","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"U Feige","year":"2002","unstructured":"Feige, U., Ofek, E., Wieder, U.: Approximating maximum edge coloring in multigraphs. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 108\u2013121. Springer, Heidelberg (2002)"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-642-13731-0_37","volume-title":"Algorithm Theory - SWAT 2010","author":"M Kami\u0144ski","year":"2010","unstructured":"Kami\u0144ski, M., Kowalik, \u0141.: Approximating the maximum 3- and 4-edge-colorable subgraph. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 395\u2013407. Springer, Heidelberg (2010)"},{"key":"16_CR11","doi-asserted-by":"publisher","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":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BFb0029574","volume-title":"Online Algorithms","author":"HA Kierstead","year":"1998","unstructured":"Kierstead, H.A.: Coloring graphs on-line. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol. 1442, pp. 281\u2013305. Springer, Heidelberg (1998)"},{"issue":"17","key":"16_CR13","doi-asserted-by":"publisher","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. Discret. Appl. Math. 157(17), 3593\u20133600 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"12","key":"16_CR14","doi-asserted-by":"publisher","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. Discret. Math. 309(12), 4166\u20134170 (2009)","journal-title":"Discret. Math."},{"issue":"2","key":"16_CR15","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"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: FOCS, pp. 222\u2013227 (1977)","key":"16_CR16","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18263-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:22:22Z","timestamp":1676938942000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18263-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319182629","9783319182636"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18263-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}