{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T05:26:31Z","timestamp":1761197191974},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,8,14]],"date-time":"2013-08-14T00:00:00Z","timestamp":1376438400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1007\/s00453-013-9819-7","type":"journal-article","created":{"date-parts":[[2013,8,13]],"date-time":"2013-08-13T19:01:56Z","timestamp":1376420516000},"page":"92-111","source":"Crossref","is-referenced-by-count":15,"title":["Online Coloring of Bipartite Graphs with and without Advice"],"prefix":"10.1007","volume":"70","author":[{"given":"Maria Paola","family":"Bianchi","sequence":"first","affiliation":[]},{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Lucia","family":"Keller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,8,14]]},"reference":[{"issue":"2","key":"9819_CR1","doi-asserted-by":"crossref","first-page":"469","DOI":"10.2307\/2272247","volume":"41","author":"D.R. Bean","year":"1976","unstructured":"Bean, D.R.: Effective coloration. J. Symb. Log. 41(2), 469\u2013480 (1976)","journal-title":"J. Symb. Log."},{"key":"9819_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-642-29344-3_6","volume-title":"Proc. of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)","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: Proc. of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012). LNCS, vol. 7256, pp. 61\u201372. Springer, Berlin (2012)"},{"key":"9819_CR3","series-title":"LNCS","first-page":"331","volume-title":"Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009)","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: Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009). LNCS, vol. 5878, pp. 331\u2013340. Springer, Berlin (2009)"},{"key":"9819_CR4","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)"},{"key":"9819_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/978-3-540-77566-9_21","volume-title":"Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008)","author":"S. Dobrev","year":"2008","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: How much information about the future is needed? In: Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008). LNCS, vol. 4910, pp. 247\u2013258. Springer, Berlin (2008)"},{"issue":"2","key":"9819_CR6","doi-asserted-by":"crossref","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"},{"key":"9819_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/978-3-642-02927-1_36","volume-title":"Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)","author":"Y. Emek","year":"2009","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. In: Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). LNCS, vol. 5555, pp. 427\u2013438. Springer, Berlin (2009)"},{"key":"9819_CR8","volume-title":"Mathematical Constants (Encyclopedia of Mathematics and Its Applications)","author":"S.R. Finch","year":"2003","unstructured":"Finch, S.R.: Mathematical Constants (Encyclopedia of Mathematics and Its Applications). Cambridge University Press, New York (2003)"},{"key":"9819_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/978-3-642-28332-1_20","volume-title":"Proc. of the 6th International Conference on Language and Automata Theory and Applications (LATA 2012)","author":"M. Fori\u0161ek","year":"2012","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice complexity of online coloring for paths. In: Proc. of the 6th International Conference on Language and Automata Theory and Applications (LATA 2012). LNCS, vol. 7183, pp. 228\u2013239. Springer, Berlin (2012)"},{"issue":"2","key":"9819_CR10","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A. Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: On-line and first fit colorings of graphs. J. Graph Theory 12(2), 217\u2013227 (1988)","journal-title":"J. Graph Theory"},{"key":"9819_CR11","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Proc. of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 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: Proc. of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010). LNCS, vol. 6281, pp. 24\u201336. Springer, Berlin (2010)"},{"key":"9819_CR12","series-title":"Studies in Logic and the Foundations of Mathematics","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1016\/S0049-237X(98)80051-7","volume-title":"Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics","author":"H.A. Kierstead","year":"1998","unstructured":"Kierstead, H.A.: Recursive and on-line graph coloring. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B., Marek, V.W. (eds.) Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics. Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 1233\u20131269. Elsevier, Amsterdam (1998)"},{"key":"9819_CR13","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1090\/dimacs\/007\/06","volume-title":"On-Line Algorithms","author":"H.A. Kierstead","year":"1992","unstructured":"Kierstead, H.A., Trotter, W.T.: On-line graph coloring. In: McGeoch, L.A., Sleator, D.D. (eds.) On-Line Algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 85\u201392 (1992). AMS\/DIMACS\/ACM"},{"issue":"2","key":"9819_CR14","first-page":"249","volume":"45","author":"D. Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. RAIRO ITA 45(2), 249\u2013267 (2011)","journal-title":"RAIRO ITA"},{"issue":"1\u20133","key":"9819_CR15","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"L. Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L., Saks, M.E., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math. 75(1\u20133), 319\u2013325 (1989)","journal-title":"Discrete Math."},{"key":"9819_CR16","unstructured":"Sloane, N.J.A.: Sequence A000073 in the on-line encyclopedia of integer sequences. Published electronically at http:\/\/oeis.org\/A000073 (2012)"},{"issue":"4","key":"9819_CR17","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/0196-6774(92)90061-G","volume":"13","author":"S. Vishwanathan","year":"1992","unstructured":"Vishwanathan, S.: Randomized online graph coloring. J. Algorithms 13(4), 657\u2013669 (1992)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9819-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9819-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9819-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T22:46:27Z","timestamp":1563662787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9819-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,14]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["9819"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9819-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,14]]}}}