{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:05:19Z","timestamp":1743019519230,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"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-18173-8_26","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"352-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Online Edge Coloring of Planar Graphs with Advice"],"prefix":"10.1007","author":[{"given":"Jesper W.","family":"Mikkelsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-319-08001-7_12","volume-title":"Approximation and Online Algorithms","author":"A Adamaszek","year":"2014","unstructured":"Adamaszek, A., Renault, M.P., Ros\u00e9n, A., van Stee, R.: Reordering buffer management with advice. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 132\u2013143. Springer, Heidelberg (2014)"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-319-08404-6_2","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"S Albers","year":"2014","unstructured":"Albers, S., Hellwig, M.: Online makespan minimization with parallel schedules. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 13\u201325. Springer, Heidelberg (2014)"},{"issue":"5","key":"26_CR3","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. Inf. Process. Lett. 44(5), 251\u2013253 (1992)","journal-title":"Inf. Process. Lett."},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-319-04298-5_8","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K.: Tight bounds for the advice complexity of the online minimum steiner tree problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 77\u201388. Springer, Heidelberg (2014)"},{"issue":"1","key":"26_CR5","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 11(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"issue":"1","key":"26_CR6","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":"26_CR7","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 k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"26_CR8","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":"26_CR9","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."},{"issue":"2","key":"26_CR10","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."},{"key":"26_CR11","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: Advice complexity for a class of online problems. In: STACS. LIPIcs, vol. 30, pp. 116\u2013129 (2015). http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2014.174"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-319-04921-2_17","volume-title":"Language and Automata Theory and Applications","author":"J Boyar","year":"2014","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the list update problem with advice. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 210\u2013221. Springer, Heidelberg (2014)"},{"key":"26_CR13","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. In: STACS. LIPIcs, vol. 25, pp. 174\u2013186 (2014)"},{"issue":"1","key":"26_CR14","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/0196-6774(90)90032-A","volume":"11","author":"M Chrobak","year":"1990","unstructured":"Chrobak, M., Nishizeki, T.: Improved edge-coloring algorithms for planar graphs. J. Algorithms 11(1), 102\u2013116 (1990)","journal-title":"J. Algorithms"},{"issue":"3","key":"26_CR15","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s00453-007-9044-3","volume":"50","author":"R Cole","year":"2008","unstructured":"Cole, R., Kowalik, L.: New linear-time algorithms for edge-coloring planar graphs. Algorithmica 50(3), 351\u2013368 (2008)","journal-title":"Algorithmica"},{"key":"26_CR16","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":"1","key":"26_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s00224-014-9592-2","volume":"56","author":"S Dobrev","year":"2015","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Advice complexity of maximum independent set in sparse and bipartite graphs. Theor. Comput. Syst. 56(1), 197\u2013219 (2015)","journal-title":"Theor. Comput. Syst."},{"issue":"3","key":"26_CR18","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."},{"issue":"24","key":"26_CR19","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":"26_CR20","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)"},{"issue":"4","key":"26_CR21","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"26_CR22","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":"26_CR23","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley (2011)"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"77","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, 77\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"26_CR25","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: SODA, pp. 359\u2013364 (1996)"},{"issue":"4","key":"26_CR26","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77(4), 453\u2013465 (1916)","journal-title":"Math. Ann."},{"issue":"1","key":"26_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: A statistical adversary for on-line algorithms. In: On-Line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 79\u201383 (1991)","DOI":"10.1090\/dimacs\/007\/05"},{"key":"26_CR29","unstructured":"Renault, M.P., Ros\u00e9n, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. CoRR, abs\/1311.7589 (2013)"},{"key":"26_CR30","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":"26_CR31","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"},{"key":"26_CR32","unstructured":"Stiebitz, M., Scheide, D., Toft, B., Favrholdt, L.M.: Graph Edge Coloring: Vizing\u2019s Theorem and Goldberg\u2019s Conjecture. Wiley (2012)"},{"key":"26_CR33","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a $$p$$-graph (in Russian). Metody Diskret. Analiz. 3, 25\u201330 (1964)","journal-title":"Metody Diskret. Analiz."},{"key":"26_CR34","first-page":"9","volume":"5","author":"VG Vizing","year":"1965","unstructured":"Vizing, V.G.: Critical graphs with given chromatic class (in Russian). Metody Diskret. Analiz. 5, 9\u201317 (1965)","journal-title":"Metody Diskret. Analiz."},{"key":"26_CR35","doi-asserted-by":"crossref","unstructured":"Zhou, X., Nishizeki, T.: Edge-coloring and f-coloring for various classes of graphs. J. Graph Algorithms Appl. 3(1) (1999)","DOI":"10.7155\/jgaa.00012"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:59:00Z","timestamp":1676941140000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_26","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":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}