{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:35:37Z","timestamp":1725521737127},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540921813"},{"type":"electronic","value":"9783540921820"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92182-0_11","type":"book-chapter","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T02:38:06Z","timestamp":1228876686000},"page":"89-99","source":"Crossref","is-referenced-by-count":2,"title":["Comparing First-Fit and Next-Fit for Online Edge Coloring"],"prefix":"10.1007","author":[{"given":"Martin R.","family":"Ehmsen","sequence":"first","affiliation":[]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[]},{"given":"Jens S.","family":"Kohrt","sequence":"additional","affiliation":[]},{"given":"Rodica","family":"Mihai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"11_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. Information Processing Letters\u00a044(5), 251\u2013253 (1992)","journal-title":"Information Processing Letters"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica\u00a011(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Boyar, J., Ehmsen, M.R., Larsen, K.S.: Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem. In: Approximation and Online Algorithms, pp. 95\u2013107 (2006)","DOI":"10.1007\/11970125_8"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Transactions on Algorithms\u00a03(22) (2007)","DOI":"10.1145\/1240233.1240245"},{"key":"11_CR5","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. Journal of Computer and System Sciences\u00a073, 818\u2013843 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1383369.1383379","volume":"4","author":"J. Boyar","year":"2008","unstructured":"Boyar, J., Medvedev, P.: The relative worst order ratio applied to seat reservation. ACM Transactions on Algorithms\u00a04(4), article 48, 22 pages (2008)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"11_CR7","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s10878-006-9005-9","volume":"12","author":"L. Epstein","year":"2006","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.: Separating online scheduling algorithms with the relative worst order ratio. Journal of Combinatorial Optimization\u00a012(4), 362\u2013385 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"11_CR8","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/s00453-002-0992-3","volume":"35","author":"L.M. Favrholdt","year":"2003","unstructured":"Favrholdt, L.M., Nielsen, M.N.: On-line edge coloring with a fixed number of colors. Algorithmica\u00a035(2), 176\u2013191 (2003)","journal-title":"Algorithmica"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences\u00a022, 407\u2013420 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A.R. Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica\u00a03, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"11_CR11","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 359\u2013364 (1996)"},{"issue":"4","key":"11_CR12","first-page":"325","volume":"9","author":"G.A. Margulis","year":"1973","unstructured":"Margulis, G.A.: Explicit constructions of concentrators. Problems of Information Transmission\u00a09(4), 325\u2013332 (1973)","journal-title":"Problems of Information Transmission"},{"key":"11_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"11_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92182-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T03:44:23Z","timestamp":1557978263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92182-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540921813","9783540921820"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92182-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}