{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:40:20Z","timestamp":1737078020865,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_19","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"232-247","source":"Crossref","is-referenced-by-count":11,"title":["Randomized Lower Bounds for Online Path Coloring"],"prefix":"10.1007","author":[{"given":"Stefano","family":"Leonardi","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Vitaletti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symposium on Foundations of Computer Science, pages 32\u201340, 1993.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 412\u2013423, 1994.","DOI":"10.1109\/SFCS.1994.365675"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"S. Ben-David, A. Borodin, R.M. Karp, G. Tardos, and A. Widgerson. On the power of randomization in on-line algorithms. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990.","DOI":"10.1145\/100216.100268"},{"key":"19_CR4","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Fiat, and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In Proceedings of the 28th ACM Symposium on Theory of Computing, pages 531\u2013540, 1996.","DOI":"10.1145\/237814.238001"},{"key":"19_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1007\/3-540-63165-8_207","volume-title":"Proceedings of the 24th International Colloqium on Automata, Languages and Programming","author":"Y. Bartal","year":"1997","unstructured":"Y. Bartal and S. Leonardi. On-line routing in all-optical networks. In Proceedings of the 24th International Colloqium on Automata, Languages and Programming, LNCS 1256, pages 516\u2013526. Springer-Verlag, 1997."},{"key":"19_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"M. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY, 1980."},{"key":"19_CR8","unstructured":"O. Gerstel, G.H. Sasaki, and R. Ramaswami. Dynamic channel assignment for WDM optical networks with little or no wavelength conversion. In Proceedings of the 34th Allerton Conference on Communication, Control, and Computing, 1996."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"M.M. Halld\u00f3rsson and M. Szegedi. Lower bounds for on-line graph coloring. In Proc. of 2th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 211\u2013216, 1992.","DOI":"10.1090\/dimacs\/007\/15"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"S. Irani. Coloring inductive graphs on-line. In Proceedings of the of 31th Annual IEEE Symposium on Foudations of Computer Science, pages 470\u2013479, 1990.","DOI":"10.1109\/FSCS.1990.89568"},{"key":"19_CR11","first-page":"143","volume":"33","author":"H. A. Kierstead","year":"1981","unstructured":"H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33:143\u2013153, 1981.","journal-title":"Congressus Numerantium"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"H. A. Kierstead and W. T. Trotter. On-line graph coloring. In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 85\u201392. AMS\/ACM, February 1991.","DOI":"10.1090\/dimacs\/007\/06"},{"key":"19_CR13","unstructured":"S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti, and A. Ros\u00e8n. On-line randomized call-control revisited. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 323\u2013332, 1998."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"L. Lov\u00e1sz","year":"1989","unstructured":"L. Lov\u00e1sz, M. Saks, and W.T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, 75:319\u2013325, 1989.","journal-title":"Discrete Mathematics"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"P. Raghavan and E. Upfal. Efficient routing in all-optical networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 133\u2013143, 1994.","DOI":"10.1145\/195058.195119"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of ACM, 28:202\u2013208, 1985.","journal-title":"Communications of ACM"},{"key":"19_CR17","unstructured":"S. Vishwanathan. Randomized on-line graph coloring. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 121\u2013130, 1990."},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"A. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the 17th Annual IEEE Symposium on Foundations of Computer Science, pages 222\u2013227, 1977.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:20:35Z","timestamp":1737076835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}