{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T01:53:39Z","timestamp":1725846819039},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662491911"},{"type":"electronic","value":"9783662491928"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-49192-8_19","type":"book-chapter","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T10:47:27Z","timestamp":1452163647000},"page":"229-240","source":"Crossref","is-referenced-by-count":4,"title":["Online Graph Coloring with Advice and Randomized Adversary"],"prefix":"10.1007","author":[{"given":"Elisabet","family":"Burjons","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Xavier","family":"Mu\u00f1oz","sequence":"additional","affiliation":[]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"key":"19_CR1","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)"},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/s00453-013-9819-7","volume":"70","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92\u2013111 (2014)","journal-title":"Algorithmica"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"H-J B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554, 95\u2013108 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"H-J B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the \n                      \n                        \n                      \n                      $$k$$\n                    -server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"19_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":"19_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H-J B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-31104-8_23","volume-title":"Structural Information and Communication Complexity","author":"S Dobrev","year":"2012","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 267\u2013278. Springer, Heidelberg (2012)"},{"issue":"3","key":"19_CR8","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. Inform. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"19_CR9","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":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-319-21398-9_33","volume-title":"Computing and Combinatorics","author":"H Gebauer","year":"2015","unstructured":"Gebauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., Smula, J.: Disjoint path allocation with sublinear advice. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 417\u2013429. Springer, Heidelberg (2015)"},{"key":"19_CR11","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)"},{"key":"19_CR12","unstructured":"Keller, L.: Complexity of optimization problems: advice and approximation. Ph.D. thesis, ETH Z\u00fcrich (2014)"},{"key":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-642-18381-2_28","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"D Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 332\u2013343. Springer, Heidelberg (2011)"},{"key":"19_CR14","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":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-319-18173-8_31","volume-title":"Algorithms and Complexity","author":"D Wehner","year":"2015","unstructured":"Wehner, D.: Advice complexity of fine-grained job shop scheduling. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 416\u2013428. Springer, Heidelberg (2015)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2016: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49192-8_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T05:09:34Z","timestamp":1559365774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49192-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662491911","9783662491928"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49192-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}