{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:33:31Z","timestamp":1743010411599,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"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_8","type":"book-chapter","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T14:41:38Z","timestamp":1429713698000},"page":"83-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Multi-Coloring with Advice"],"prefix":"10.1007","author":[{"given":"Marie G.","family":"Christ","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2004.08.002","volume":"70","author":"S Albers","year":"2005","unstructured":"Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. J. Comput. Syst. Sci. 70(2), 145\u2013175 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-04298-5_9","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K., B\u00f6ckenhauer, H.-J., Fori\u0161ek, M., Gebauer, H., Hromkovi\u010d, J., Krug, S., Smula, J., Steffen, B.: On the power of advice and randomization for the disjoint path allocation problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 89\u2013101. Springer, Heidelberg (2014)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-642-32241-9_44","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2012","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 519\u2013530. Springer, Heidelberg (2012)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the $$k$$-server problem. ICALP. LNCS 6755, 207\u2013218 (2011)","DOI":"10.1007\/978-3-642-22006-7_18"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-10631-6_35","volume-title":"Algorithms and Computation","author":"H-J B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-29344-3_6","volume-title":"LATIN 2012: Theoretical Informatics","author":"H-J B\u00f6ckenhauer","year":"2012","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the advice complexity of the Knapsack problem. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 61\u201372. Springer, Heidelberg (2012)"},{"key":"8_CR7","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":"8_CR8","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00236-003-0124-9","volume":"40","author":"J Boyar","year":"2003","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: Extending the accommodating function. Acta Informatica 40(1), 3\u201335 (2003)","journal-title":"Acta Informatica"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-31155-0_29","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"J Boyar","year":"2012","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Access graphs results for LRU versus FIFO under relative worst order analysis. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 328\u2013339. Springer, Heidelberg (2012)"},{"key":"8_CR11","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. In Thirty-First International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 25 of LIPIcs, pp. 174\u2013186. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik GmbH, German (2014)"},{"issue":"4","key":"8_CR12","doi-asserted-by":"publisher","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":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Larsen, K.S., Nielsen, M.N.: The accommodating function: a generalization of the competitive ratio. SIAM J. Comput. 31(1), 233\u2013258 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/s00453-009-9279-2","volume":"58","author":"JW-T Chan","year":"2010","unstructured":"Chan, J.W.-T., Chin, F.Y.L., Ye, D., Zhang, Y.: Absolute and asymptotic bounds for online frequency allocation in cellular networks. Algorithmica 58(2), 498\u2013515 (2010)","journal-title":"Algorithmica"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/11940128_8","volume-title":"Algorithms and Computation","author":"JW-T Chan","year":"2006","unstructured":"Chan, J.W.-T., Chin, F.Y.L., Ye, D., Zhang, Y., Zhu, H.: Frequency allocation problems for linear cellular networks. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 61\u201370. Springer, Heidelberg (2006)"},{"issue":"5\u20136","key":"8_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00236-013-0184-4","volume":"50","author":"MG Christ","year":"2013","unstructured":"Christ, M.G., Favrholdt, L.M., Larsen, K.S.: Online multi-coloring on the path revisited. Acta Informatica 50(5\u20136), 343\u2013357 (2013)","journal-title":"Acta Informatica"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Christ, M.G., Favrholdt, L.M., Larsen, K.S.: Online multi-coloring with advice. (2014) arXiv:1409.1722 [cs.DS]","DOI":"10.1007\/978-3-319-18263-6_8"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2012.05.020","volume":"514","author":"M Chrobak","year":"2013","unstructured":"Chrobak, M., Jez, L., Sgall, J.: Better bounds for incremental frequency allocation in bipartite graphs. Theor. Comput. Sci. 514, 75\u201383 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"8_CR19","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.tcs.2009.09.019","volume":"411","author":"M Chrobak","year":"2010","unstructured":"Chrobak, M., Sgall, J.: Three results on frequency assignment in linear cellular networks. Theor. Comput. Sci. 411(1), 131\u2013137 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"8_CR20","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO Theor. Inf. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-642-35261-4_17","volume-title":"Algorithms and Computation","author":"R Dorrigiv","year":"2012","unstructured":"Dorrigiv, R., He, M., Zeh, N.: On the advice complexity of buffer management. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 136\u2013145. Springer, Heidelberg (2012)"},{"issue":"2","key":"8_CR22","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"24","key":"8_CR23","doi-asserted-by":"publisher","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-28332-1_20","volume-title":"Language and Automata Theory and Applications","author":"M Fori\u0161ek","year":"2012","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice complexity of online coloring for paths. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 228\u2013239. Springer, Heidelberg (2012)"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24\u201336. Springer, Heidelberg (2010)"},{"issue":"2","key":"8_CR26","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/25.752578","volume":"48","author":"J Janssen","year":"1999","unstructured":"Janssen, J., Kilakos, K., Marcotte, O.: Fixed preference channel assignment for cellular telephone systems. IEEE Trans. Veh. Technol. 48(2), 533\u2013541 (1999)","journal-title":"IEEE Trans. Veh. Technol."},{"issue":"2","key":"8_CR27","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jagm.1999.1068","volume":"36","author":"J Janssen","year":"2000","unstructured":"Janssen, J., Krizanc, D., Narayanan, L., Shende, S.M.: Distributed online frequency assignment in cellular networks. J. Algorithms 36(2), 119\u2013151 (2000)","journal-title":"J. Algorithms"},{"key":"8_CR28","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"},{"issue":"2","key":"8_CR29","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. RAIRO Theor. Inf. Appl 45(2), 249\u2013267 (2011)","journal-title":"RAIRO Theor. Inf. Appl"},{"key":"8_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-642-30642-6_23","volume-title":"Computer Science \u2013 Theory and Applications","author":"D Komm","year":"2012","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of the set cover problem. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 241\u2013252. Springer, Heidelberg (2012)"},{"key":"8_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-38768-5_7","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2013","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Krug, S., Steffen, B.: On the advice complexity of the online L(2,1)-coloring problem on paths and cycles. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 53\u201364. Springer, Heidelberg (2013)"},{"issue":"2","key":"8_CR32","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1002\/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G","volume":"36","author":"C McDiarmid","year":"2000","unstructured":"McDiarmid, C., Reed, B.A.: Channel assignment and weighted coloring. Networks 36(2), 114\u2013117 (2000)","journal-title":"Networks"},{"key":"8_CR33","first-page":"71","volume-title":"Channel Assignment and Graph Multicoloring","author":"L Narayanan","year":"2002","unstructured":"Narayanan, L.: Channel Assignment and Graph Multicoloring, pp. 71\u201394. Wiley, New York (2002)"},{"issue":"3","key":"8_CR34","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/s004530010067","volume":"29","author":"L Narayanan","year":"2001","unstructured":"Narayanan, L., Shende, S.M.: Static frequency assignment in cellular networks. Algorithmica 29(3), 396\u2013409 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR35","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s00453-001-0099-2","volume":"32","author":"L Narayanan","year":"2002","unstructured":"Narayanan, L., Shende, S.M.: Corrigendum: static frequency assignment in cellular networks. Algorithmica 32(4), 679 (2002)","journal-title":"Algorithmica"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-38233-8_29","volume-title":"Algorithms and Complexity","author":"S Seibert","year":"2013","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice complexity of the online coloring problem. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 345\u2013357. Springer, Heidelberg (2013)"},{"issue":"2","key":"8_CR37","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"},{"issue":"1","key":"8_CR38","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jalgor.2004.09.001","volume":"55","author":"P Sparl","year":"2005","unstructured":"Sparl, P., Zerovnik, J.: 2-local 4\/3-competitive algorithm for multicoloring hexagonal graphs. J. Algorithms 55(1), 29\u201341 (2005)","journal-title":"J. Algorithms"},{"key":"8_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-21286-4_7","volume-title":"Algorithms and Models for the Web Graph","author":"R Witkowski","year":"2011","unstructured":"Witkowski, R., \u017derovnik, J.: 1-local 33\/24-competitive algorithm for multicoloring hexagonal graphs. In: Frieze, A., Horn, P., Pra\u0142at, P. (eds.) WAW 2011. LNCS, vol. 6732, pp. 74\u201384. Springer, Heidelberg (2011)"}],"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_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:15:13Z","timestamp":1676016913000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18263-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319182629","9783319182636"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18263-6_8","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"}}]}}